LeetCode Solutions Blog

Find the City With the Smallest Number of Neighbors at a Threshold Distance

Number: 1456

Difficulty: Medium

Paid? No

Problem Description

Given n cities and an array of bidirectional weighted edges, find the city that can reach the fewest number of other cities within a given distance threshold. If there are several such cities, return the one with the greatest index.

Key Insights

Compute shortest paths between every pair of cities.
Use the Floyd-Warshall algorithm which is efficient for n up to 100.
Count for each city how many other cities are reachable within the distance threshold.
Return the city with the minimum count (and the greatest index in case of tie).

Space and Time Complexity

Time Complexity: O(n^3) due to the triple nested loops of the Floyd-Warshall algorithm. Space Complexity: O(n^2) to store the distance matrix.

Solution

We start by initializing a distance matrix of size n x n. For each direct edge, we update the matrix with the given weight. We set the distance from a city to itself as 0 and all other unavailable routes as infinity. Then, we use the Floyd-Warshall algorithm to compute the shortest paths between all pairs of cities by iterating over each possible intermediate city. Once we have the shortest distances, we count the number of cities reachable from each city where the distance is less than or equal to the threshold. The final answer is the city with the smallest count; if there is a tie, return the city with the greatest index. Key data structures include:

A 2D array to serve as the distance matrix.
Loops for updating the matrix using the Floyd-Warshall algorithm.

Code Solutions

# Python solution using Floyd-Warshall algorithm

def findTheCity(n, edges, distanceThreshold):
    # Initialize the distance matrix with infinity values
    INF = float('inf')
    distances = [[INF] * n for _ in range(n)]
    
    # Set the distance from each city to itself as 0
    for i in range(n):
        distances[i][i] = 0
    
    # Update distance matrix with the given edge weights (bidirectional)
    for u, v, w in edges:
        distances[u][v] = w
        distances[v][u] = w
    
    # Use Floyd-Warshall to calculate all-pairs shortest path
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distances[i][k] + distances[k][j] < distances[i][j]:
                    distances[i][j] = distances[i][k] + distances[k][j]
    
    # Determine the city with the smallest number of reachable neighbors within distanceThreshold
    result_city = -1
    min_reachable = n + 1  # initialize with a large number
    
    for i in range(n):
        count = 0
        for j in range(n):
            if i != j and distances[i][j] <= distanceThreshold:
                count += 1
        # Update result: if count is less than current minimum, or same count and current city is greater index
        if count < min_reachable or (count == min_reachable and i > result_city):
            min_reachable = count
            result_city = i
    
    return result_city

# Example usage:
n = 4
edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
distanceThreshold = 4
print(findTheCity(n, edges, distanceThreshold))  # Expected output: 3