Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Find the City With Fewest Reachable

LeetCode #1334Medium
Floyd-Warshall all-pairs, then count

Given an undirected weighted graph of cities and a distance threshold, find the city that can reach the fewest other cities within the threshold distance. If several cities tie, return the one with the largest index.

Asked atAmazonGoogle
step 1 / 20
undirected weighted · threshold = 4
3141
0
1
2
3
all-pairs distance matrix
from \ to0123
003∞∞
13014
2∞101
3∞410
Floyd-Warshall + count
▸
1dist[i][j] = w (edges), 0 (i==i), ∞ else
2for k in 0..n-1:
3    for i, j:
4        if dist[i][k] + dist[k][j] < dist[i][j]:
5            dist[i][j] = dist[i][k] + dist[k][j]
6// score cities
7for each city i:
8    count j with dist[i][j] <= threshold
9pick fewest count; tie → largest index
state
  • n4
  • threshold4
  • tie-breaklargest id

line 1For every city, count how many OTHER cities it can reach with a shortest-path distance ≤ 4. Then return the city with the FEWEST reachable neighbours; if several tie, return the one with the LARGEST index. We need shortest paths between ALL pairs — perfect for Floyd-Warshall.