Find the city with the smallest number of neighbors
HardFloyd-Warshall, then count close neighbours
Problem
Find the city with the fewest other cities reachable within a distance threshold (ties: largest index).
Floyd-Warshall gives all shortest distances; pick the city with the fewest neighbours within the threshold.
The idea
First get all-pairs shortest distances with Floyd-Warshall (shown here). Then, for each city, count how many other cities lie within the distance threshold. The answer is the city with the fewest such neighbours — and on a tie, the one with the greatest index.
Step 1 of 11. Floyd-Warshall finds the shortest distance between every pair of nodes. Here is the weighted graph we will measure.
1dist[i][j] = edge(i,j) or ∞, and dist[i][i] = 02for k in nodes:3 for i, for j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])4then count reachable cities per city; pick the smallest (largest index on tie)Input
- nodes
- 4, 5 edges
Memory
- cells marked
- —
- rows
- —
- cols
- —
- via k
- —
Output
- all-pairs
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], threshold=4
- Output:
- 3
- Explanation:
- City 3 reaches the fewest others within 4.
Example 2
- Input:
- n=5, edges=[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], threshold=2
- Output:
- 0
- Explanation:
- City 0 has the fewest reachable neighbours.
Example 3
- Input:
- n=2, edges=[[0,1,1]], threshold=1
- Output:
- 1
- Explanation:
- Tie → the higher-numbered city 1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.