Problem Statement

Find City With Smallest Number of Neighbors at a Threshold Distance

Picture a map of cities with roads between them. Each road has a length. You are given a number called the threshold, which is the longest total trip you are willing to make. For each city, we count how many other cities you can reach without your trip going over the threshold. We want the city that can reach the fewest other cities. If two cities tie with the same count, we pick the one with the bigger number (the larger index). To do this we use a method called Floyd-Warshall. Floyd-Warshall finds the shortest possible trip between every pair of cities, all at once. Once we know the shortest trip between every pair, counting reachable cities is easy.

mediumGraphGraphsTime: O(V³) · Space: O(V²)

Signals to notice

city with fewest reachable neighbors within thresholdall-pairs shortest pathsFloyd-Warshall

Brute force first

Dijkstra from each city — O(V² log V + VE).

The key insight

Floyd-Warshall O(V³). Count reachable neighbors per city. Return city with fewest (largest number for ties).

Trace it on `n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], threshold=4`

init dist: d(0,1)=3, d(1,2)=1, d(1,3)=4, d(2,3)=1, diagonal=0, rest=inf
Floyd-Warshall relaxes: d(0,2)=4 (0->1->2), d(1,3)=2 (1->2->3), d(0,3)=5 (0->1->2->3)
final dist rows -> 0:[0,3,4,5], 1:[3,0,1,2], 2:[4,1,0,1], 3:[5,2,1,0]
city 0: neighbors with d<=4 = {1,2} -> count=2; count<=inf so minCount=2, result=0
city 1: {0,2,3} -> count=3; 3<=2 false, result stays 0
city 2: {0,1,3} -> count=3; 3<=2 false, result stays 0
city 3: {1,2} (d=2,1) -> count=2; 2<=2 true (tie, larger index), minCount=2, result=3
return 3

What must stay true

Floyd-Warshall gives all-pairs distances. Counting neighbors ≤ threshold is O(V) per city.

Shape of the loop

dist = inf matrix; dist[i][i]=0; dist[u][v]=dist[v][u]=w for each edge
for k in cities: for i in cities: for j in cities:
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
best = -1; minCount = inf
for i in cities: count = #{ j != i : dist[i][j] <= threshold }
    if count <= minCount: minCount, best = count, i   # <= keeps larger index on ties
return best

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not checking ties — return the largest-numbered city among those with equal neighbor counts.

Graphs Pattern