Find City With Smallest Number of Neighbors at a Threshold Distance
mediumTime: O(V³)Space: O(V²)
Signals to notice
city with fewest reachable neighbors within thresholdall-pairs shortest pathsFloyd-Warshall
Brute force first
Dijkstra from each city — O(V² log V + VE).
The key insight
Floyd-Warshall O(V³). Count reachable neighbors per city. Return city with fewest (largest number for ties).
What must stay true
Floyd-Warshall gives all-pairs distances. Counting neighbors ≤ threshold is O(V) per city.
Easy way to go wrong
Not checking ties — return the largest-numbered city among those with equal neighbor counts.