This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.
Graphs
Find City with Fewest Reachable
medium
DESCRIPTION (inspired by Leetcode.com)
A regional planning committee wants to identify the most "isolated" city in a road network. Given n cities connected by bidirectional roads with varying distances, find the city that can reach the fewest other cities within a given distance threshold.
If multiple cities have the same minimum count, return the city with the highest number.
Note: The same pair of cities may be directly connected by more than one road. The distance between two cities is the shortest total distance across all possible routes.
Example 1:
Input:
n = 4
edges = [[0,1,3], [1,2,1], [1,3,4], [2,3,1]]
distanceThreshold = 4
Output:
3
Explanation: After computing shortest paths, city 3 can reach cities 1 (distance 2) and 2 (distance 1) within the threshold — 2 reachable. City 0 can also reach 2 cities, but city 3 wins the tie by having the highest number.
Example 2:
Input:
n = 5
edges = [[0,1,2], [0,4,8], [1,2,3], [1,4,2], [2,3,1], [3,4,1]]
distanceThreshold = 2
Output:
0
Explanation: With threshold 2, city 0 can only reach city 1 (distance 2). Other cities can reach more neighbors. City 0 has the fewest reachable.