Find the City With the Smallest Number of Neighbors
Medium · Graphs · Graph · Shortest Path · Dynamic Programming
Problem
There are n cities numbered 0 to n - 1. Each edges[i] = [from, to, weight] is a two-way road of length weight. You are also given an integer distanceThreshold.
For every city, count how many other cities it can reach along some path whose total length is at most distanceThreshold. Return the city with the smallest such count. If several cities tie for the smallest count, return the one with the largest number.
Examples
Input: n = 4, edges = [[0,1,2],[1,2,3],[2,3,1]], distanceThreshold = 3 Output: 3
Cities 0 and 3 each reach one other city within 3; the tie goes to the larger number, 3.
Input: n = 3, edges = [[0,1,1],[1,2,5]], distanceThreshold = 2 Output: 2
City 2 reaches nobody within 2, while cities 0 and 1 each reach one city.
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
City 0 reaches only city 1 within 2; every other city reaches at least two.
Constraints
- 2 <= n <= 100
- 1 <= len(edges) <= n * (n - 1) / 2
- edges[i] == [from, to, weight] with 0 <= from < to < n
- 1 <= weight, distanceThreshold <= 10^4
- All (from, to) pairs are distinct
Approaches
- Baseline: Bellman–Ford from every city — time O(n^2 · E), space O(n)
Follow-up
Floyd–Warshall is the simplest all-pairs method; for sparse graphs a bounded Dijkstra from each city does less work. The use cases return the full table of counts, and pick the best-connected city instead of the least connected.
Related problems
Start free on Cariara · Coding problems · System design studio
