#1334 Find the City With the Smallest Number of Neighbors at a Threshold Distance
frequently reported atAmazon
the problem
In plain words
n cities are joined by two-way weighted roads. For each city, count how many other cities are reachable with total distance ≤ distanceThreshold. Return the city with the smallest count; on a tie, return the one with the largest number.
in n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
out 3
Cities 0 and 3 each reach 2 others; 3 is larger.
in n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
out 0
- 2 ≤ n ≤ 100
- 1 ≤ edges.length ≤ n·(n − 1)/2
- 1 ≤ weight, distanceThreshold ≤ 10⁴
- All pairs distinct
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFloyd–Warshall
Every city needs distances to every other city — that's all pairs. With n ≤ 100, Floyd–Warshall's 10⁶ steps are nothing.
solutions
From brute force to optimal
Run Dijkstra n times, stop each run once distances pass the threshold, count the reachable cities.
- Build an undirected adjacency list.
- For each source: Dijkstra, count dist ≤ threshold.
- Keep the smallest count;
<=breaks ties toward larger indices.
n runs of Dijkstra. Faster than Floyd when the graph is sparse.
Adjacency list, one dist array and heap at a time.
class Solution { public int findTheCity(int n, int[][] edges, int distanceThreshold) { List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { // roads are two-way adj.get(e[0]).add(new int[] {e[1], e[2]}); adj.get(e[1]).add(new int[] {e[0], e[2]}); } int answer = -1, fewest = Integer.MAX_VALUE; for (int src = 0; src < n; src++) { int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); pq.offer(new int[] {0, src}); while (!pq.isEmpty()) { int[] top = pq.poll(); int d = top[0], u = top[1]; if (d > dist[u]) continue; if (d > distanceThreshold) break; // everything left is too far for (int[] next : adj.get(u)) if (d + next[1] < dist[next[0]]) { dist[next[0]] = d + next[1]; pq.offer(new int[] {dist[next[0]], next[0]}); } } int reachable = 0; for (int v = 0; v < n; v++) if (v != src && dist[v] <= distanceThreshold) reachable++; if (reachable <= fewest) { // <= : ties go to the larger index fewest = reachable; answer = src; } } return answer; }}Fill an n × n distance matrix with three loops, then count each row.
- dist = ∞, diagonal 0, each road filled in both directions.
- For k, i, j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
- For each row count entries ≤ threshold; pick the smallest count, ties → larger index.
Three nested loops over n = 100 → 10⁶ steps.
The distance matrix.
class Solution { public int findTheCity(int n, int[][] edges, int distanceThreshold) { final int INF = 1_000_000_000; int[][] dist = new int[n][n]; for (int[] row : dist) Arrays.fill(row, INF); for (int i = 0; i < n; i++) dist[i][i] = 0; for (int[] e : edges) { dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]); dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]); } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; int answer = -1, fewest = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int reachable = 0; for (int j = 0; j < n; j++) if (i != j && dist[i][j] <= distanceThreshold) reachable++; if (reachable <= fewest) { fewest = reachable; answer = i; } } return answer; }}Dry run
in the room
How to say it in the interview
talk track
- Spot "every city" → all pairs. Check n: 100 → Floyd is fine.
- Explain the tie-break: iterate i upward and use
<=.
traps
- Counting the city itself.
- Using
<instead of<=and returning the smaller index on ties. - Filling only one direction of an undirected road.
what they ask next
Follow-ups
n = 10⁴, sparse roads?
Floyd would need 10¹² steps. Use Dijkstra from each city with an early stop at the threshold.
before you submit
Edge cases to test
- Tie on the count → the city with the larger number (
<=while scanning upward). - No city reaches any other → every count is 0 → return n − 1.
- Never count the city itself (dist[i][i] = 0 is always within the threshold).
practise next
Similar problems
- #743Network Delay TimeMediumin Shortest Paths
- #1976Number of Ways to Arrive at DestinationMediumin Shortest Paths