Find City With Smallest Number of Neighbors at a Threshold Distance medium
Description
There are n cities numbered from 0 to n - 1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional weighted edge, and an integer distanceThreshold.
Return the city with the smallest number of cities reachable through some path of distance at most distanceThreshold. If there are multiple such cities, return the city with the greatest number.
The distance is the sum of edge weights along the path.
Examples
> Case 1:
n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
# City 0 reaches: {1, 2, 3} (3 cities)
# City 1 reaches: {0, 2, 3} (3 cities)
# City 2 reaches: {0, 1, 3} (3 cities)
# City 3 reaches: {1, 2} (2 cities) ← smallest, return 3
> Case 2:
n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0Constraints
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 21 <= distanceThreshold <= 10^41 <= weight_i, distanceThreshold <= 10^4
State design
n ≤ 100 is the giveaway. Floyd-Warshall is O(n³) = 10^6 — instant.
After computing all-pairs distances, for each city count how many other cities are within distanceThreshold. Take the city with the smallest count, breaking ties by larger city index.
You could run Dijkstra from every source in O(n · (n + E) log n), but the code is twice as long and you’d be reinventing the wheel.
Code
Analysis
- Time:
O(n³)for Floyd-Warshall +O(n²)for the counting pass. - Space:
O(n²)for the distance matrix.
The tie-breaking rule (“largest city index”) makes the count <= best_count (vs <) comparison the right one — i iterates in increasing order, so the last city to match the best count wins.
Same skin
- Course Schedule IV — Floyd-Warshall variant on reachability (Boolean OR, not min sum).
- Number of Ways to Reach Destination — Floyd-Warshall + DP for path counting.
- Transitive closure — same triple loop, AND/OR instead of
+/min.