Watch 10 video solutions for Find the City With the Smallest Number of Neighbors at a Threshold Distance, a medium level problem involving Dynamic Programming, Graph, Shortest Path. This walkthrough by take U forward has 137,652 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.
Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.
Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.
Example 1:
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 Output: 3 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 4 for each city are: City 0 -> [City 1, City 2] City 1 -> [City 0, City 2, City 3] City 2 -> [City 0, City 1, City 3] City 3 -> [City 1, City 2] Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.
Example 2:
Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 Output: 0 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 2 for each city are: City 0 -> [City 1] City 1 -> [City 0, City 4] City 2 -> [City 3, City 4] City 3 -> [City 2, City 4] City 4 -> [City 1, City 2, City 3] The city 0 has 1 neighboring city at a distanceThreshold = 2.
Constraints:
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= fromi < toi < n1 <= weighti, distanceThreshold <= 10^4(fromi, toi) are distinct.Problem Overview: You are given n cities connected by weighted edges. A city can reach another if the shortest path distance is ≤ distanceThreshold. The goal is to return the city that can reach the smallest number of neighbors. If multiple cities tie, choose the one with the greatest index.
This is a classic all‑pairs shortest path problem. The key step is computing the minimum distance between every pair of cities, then counting how many are within the threshold for each city.
Approach 1: Floyd‑Warshall Algorithm (Time: O(n^3), Space: O(n^2))
Floyd‑Warshall computes shortest paths between every pair of nodes using dynamic programming. Initialize an n x n distance matrix with edge weights and set dist[i][i] = 0. Then iterate through each intermediate node k and update distances with dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After processing all intermediates, every cell contains the shortest path distance. Iterate through each city and count how many other cities have dist[i][j] ≤ distanceThreshold. Track the city with the smallest count, breaking ties by choosing the largest index. This method is straightforward and ideal when n is small (≤100), since the cubic runtime remains manageable.
This approach directly uses concepts from dynamic programming and graph shortest‑path relaxation.
Approach 2: Run Dijkstra from Every City (Time: O(n · (E log V)), Space: O(E + V))
Instead of computing all pairs at once, run Dijkstra’s algorithm starting from each city. Build an adjacency list for the graph, then use a min‑heap priority queue to repeatedly expand the smallest distance node. For each source city, compute shortest distances to all others while ignoring paths exceeding distanceThreshold. Count how many cities are reachable within the limit. Repeat this process for every city and maintain the minimum neighbor count with the required tie‑breaking rule.
This method scales better for sparse graphs where E is much smaller than n^2. It relies on standard shortest path techniques and a priority queue.
Recommended for interviews: Both approaches are acceptable. Floyd‑Warshall demonstrates clear understanding of all‑pairs shortest path and is often simpler to implement quickly. Running Dijkstra from each node shows stronger algorithmic awareness and performs better on sparse graphs. Mention both during discussion: the cubic dynamic programming solution first, then the repeated Dijkstra optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Floyd-Warshall Algorithm | O(n^3) | O(n^2) | Best when the graph is small and you want a simple all-pairs shortest path solution |
| Dijkstra from Each Node | O(n · (E log V)) | O(E + V) | Preferred for sparse graphs where edges are far fewer than n^2 |