Given weighted undirected roads between n cities, return the city with the fewest other cities reachable within distanceThreshold. Break ties by the larger city number.
Before you code
Every city needs distances to every other city: all pairs. With n ≤ 100, Floyd-Warshall's n³ is a million steps.
Hints
- Initialize d with 0 on the diagonal, edge weights both ways and infinity elsewhere.
- Run the triple loop with k outermost.
- For each city, count the others with
d[i][j] <= threshold; keep the smallest count, preferring larger indexes on ties.
Production & complexity notes
When solving Find the city with the smallest number of neighbors at a threshold distance on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Floyd-Warshall to reinforce the underlying pattern.
What it practices
All-pairs shortest paths, from Floyd-Warshall.