Find The City With The Smallest Number Of Neighbors At A Threshold Distance - Leetcode Solution

Problem Statement:

Given a matrix of n x n representing the distance between the cities. There are m cities numbered from 0 to m-1. Given the threshold distance, we need to find the city with the smallest number of neighbors at a threshold distance. Note that the threshold distance does not count itself as a neighbor.

Solution:

First, we will create an adjacency matrix to represent the distance between the cities. Here, we will use a 2D list to represent this matrix. For the distance between city i and city j, we will store the distance in adj[i][j] and also in adj[j][i] because the distance between city i and city j is the same as the distance between city j and city i.

Then, we will iterate through each city and find the number of neighbors it has at a threshold distance. We will use a nested loop to iterate through all pairs of cities. For each pair of cities i and j, we will check if their distance is less than or equal to the threshold distance. If yes, then we will increment the number of neighbors for both cities.

After iterating through all pairs of cities, we will find the city with the smallest number of neighbors at a threshold distance and return its index.

Here is the Python code for the solution:

def findTheCity(n: int, edges: List[List[int]], distanceThreshold: int) -> int: # Create adjacency matrix adj = [[float('inf')] * n for _ in range(n)] for i, j, w in edges: adj[i][j] = w adj[j][i] = w

# Floyd Warshall algorithm to find shortest distances between all pairs of cities
for k in range(n):
    for i in range(n):
        for j in range(n):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

# Find number of neighbors for each city at threshold distance
min_neighbors = float('inf')
min_index = 0
for i in range(n):
    neighbors = 0
    for j in range(n):
        if i != j and adj[i][j] <= distanceThreshold:
            neighbors += 1
    if neighbors <= min_neighbors:
        min_neighbors = neighbors
        min_index = i

return min_index

Time Complexity: O(n^3) - Since we are using the Floyd Warshall algorithm to find the shortest distance between all pairs of cities, the time complexity of the solution is O(n^3).

Space Complexity: O(n^2) - Since we are storing the adjacency matrix to represent the distance between the cities, the space complexity of the solution is O(n^2).

Overall, this solution should be able to handle the given problem for large values of n and distanceThreshold.

1