Find City With Smallest Number of Neighbors at a Threshold Distance
mediumTime: O(V³)Space: O(V²)
Recognize the pattern
city with fewest reachable neighbors within thresholdall-pairs shortest pathsFloyd-Warshall
Brute force idea
Dijkstra from each city — O(V² log V + VE).
Better approach
Floyd-Warshall O(V³). Count reachable neighbors per city. Return city with fewest (largest number for ties).
Key invariant
Floyd-Warshall gives all-pairs distances. Counting neighbors ≤ threshold is O(V) per city.
Watch out for
Not checking ties — return the largest-numbered city among those with equal neighbor counts.