Find The City With The Smallest Number Of Neighbors
01 · Problem
There are n cities numbered 0 to n - 1. Each entry edges[i] = [from, to, weight] is an undirected road of length weight between two cities. You are also given an integer distanceThreshold.
For each city, count how many other cities can be reached through some path whose total length is at most distanceThreshold. Return the city with the smallest such count. If several cities tie, return the one with the largest index.
02 · Examples
n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
3
Within distance 4: city 0 reaches {1,2}, city 1 reaches {0,2,3}, city 2 reaches {0,1,3}, city 3 reaches {1,2}. Cities 0 and 3 tie with 2 neighbours; the larger index 3 is returned.
n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
0
City 0 reaches only city 1 within distance 2, while every other city reaches at least two others, so the answer is 0.
n = 3, edges = [[0,1,5]], distanceThreshold = 3
2
No road is short enough, so every city has 0 reachable neighbours. All three tie and the largest index, 2, is returned.
03 · Constraints
- 012 <= n <= 100
- 021 <= edges.length <= n * (n - 1) / 2
- 03edges[i].length == 3, 0 <= from < to < n
- 041 <= weight, distanceThreshold <= 104
- 05All pairs (from, to) are distinct
04 · Optimal complexity
- Time
- O(n * E log n)
- Space
- O(n + E)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.