Find the City With the Smallest Number of Neighbors at a Threshold Distance
Medium Floyd-Warshall
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a weighted undirected graph of n cities, count for each city how many others are within distanceThreshold. Return the city with the fewest such neighbours; on ties, the one with the greatest number.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: which city can reach the fewest others within the distance limit?
Why this works: Floyd-Warshall gives all-pairs shortest paths by trying every city k as a middle stop.
Example: 4 cities, threshold 4
reachable counts: 0→2, 1→3, 2→3, 3→2tie between 0 and 3 → pick the larger, 3
✦Hints open one at a time
↗Approach
Initialise a distance matrix with edges (both directions), 0 on the diagonal, infinity elsewhere. Triple loop with k outermost. Then count reachable cities per row and pick the best, preferring later indexes on ties.
</>Solution (Java)
import java.util.*;
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
final int INF = 1_000_000_000;
int[][] d = new int[n][n];
for (int[] row : d) Arrays.fill(row, INF);
for (int i = 0; i < n; i++) d[i][i] = 0;
for (int[] e : edges) {
d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
d[e[1]][e[0]] = Math.min(d[e[1]][e[0]], e[2]);
}
for (int k = 0; k < n; k++) // k outermost
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
int best = -1, fewest = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) if (i != j && d[i][j] <= distanceThreshold) count++;
if (count <= fewest) { // <= keeps the larger index on ties
fewest = count;
best = i;
}
}
return best;
}
}!Common mistake
Putting k in an inner loop — k must be the outermost loop for Floyd-Warshall to be correct.
- Time: O(n³).
- Space: O(n²).