Find the City With the Smallest Number of Neighbors at a Threshold Distance

There are n cities (0 .. n-1) connected by bidirectional weighted edges[i] = [u, v, w]. Return the city with the smallest number of other cities reachable within a total distance ≤ threshold. If several cities tie, return the one with the greatest index.

Hints

· Stuck? Reveal one nudge at a time.

You need shortest distances between all pairs, not just direct edges.

Compute the all-pairs matrix (Floyd-Warshall), then count each city's neighbours within threshold.

Return the city with the fewest; on ties pick the largest index (scan with ≤).

Common doubts

A city might reach another cheaply via intermediate cities even without a direct road, so you need true shortest distances.

Scanning cities 0..n-1, using ≤ means a later city with an equal count overwrites the earlier best, so the greatest index survives.

Both give the same matrix; Floyd-Warshall is simpler to code and fine here since n is small and graphs can be dense.

Interview follow-ups

· What an interviewer asks next.

Reachability becomes asymmetric; count only cities reachable FROM each city.

Prefer Dijkstra per source (with a heap) on sparse graphs; Floyd-Warshall's O(n³) becomes prohibitive.

Fun facts

LeetCode 1334 — a clean 'all-pairs then count' application of Floyd-Warshall.
The ≤ tie-break trick is a tidy way to encode 'largest index wins' in one pass.

Asked at

AmazonGoogle

Frequently Sometimes Occasionally

Example 1

Input: n = 4, edges = [[0,1,3],[1,2,1],[2,3,4],[0,3,7]], threshold = 4
Output: 3
City 3 reaches only city 2 within distance 4 — the fewest.

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
City 0 reaches the fewest (just city 1) within distance 2.

Constraints

- 1 <= n <= 100 - 0 <= edges.length <= n*(n-1)/2 - 1 <= w <= 10^4 - 0 <= threshold <= 10^4

Two questions stack here: all-pairs shortest distances, then count and choose. Compute the distance between every pair (Floyd-Warshall is the tidy choice), then for each city count how many others sit within threshold. Return the city with the fewest such neighbours, breaking ties toward the largest index — which you get for free by scanning 0 .. n-1 and using a ≤ comparison so a later city overwrites an equal earlier one.

Floyd-Warshall is O(n³); the brute alternative runs Dijkstra from every city for the same all-pairs matrix, O(n·(n+E) log n). Both feed the identical count-and-pick step.

Prerequisites

Before you start

· Concepts used directly in the solution.

All-pairs distances. Floyd-Warshall or Dijkstra ×n.

Tie rule. largest index wins.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Count includes the city itself?”

No — only other reachable cities.

“Tie-breaking?”

Return the city with the greatest index.

The ideal opening — say it like this

I compute all-pairs shortest distances with Floyd-Warshall, then count each city's neighbours within the threshold.

I return the city with the fewest, scanning in order with ≤ so the largest index wins ties.

Understand the problem

Worked example — n = 4, edges [[0,1,3],[1,2,1],[2,3,4],[0,3,7]], threshold = 4

city 3 reaches {2} within 4 -> count 1 (fewest); it's also the largest index
answer = 3

Key observations

1Aha

Need shortest distances, not direct edges

Multi-hop routes can fall under the threshold.

2Aha

Count per city, then min

Fewest reachable neighbours wins.

3Aha

≤ scan gives the largest-index tie-break

A later equal city overwrites the earlier one.

Brute force vs optimal

	Dijkstra per city	Floyd-Warshall
All-pairs via	n Dijkstra runs	one O(n³) DP
Time	O(n·(n+E) log n)	O(n³)
Then	count + pick	count + pick

Both compute the same distances and pick the same city. Full code is in the Approaches selector below.

Summary

Key takeaway

Compute all-pairs shortest distances (Floyd-Warshall), count each city's neighbours within threshold, and return the city with the fewest — largest index on ties. O(n³).

all-pairs distances; count[i] = #{j != i : dist[i][j] <= threshold}
answer = argmin count with largest-index tie-break