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

At a Glance

Topic: advanced-graphs
Pattern: Floyd-Warshall / all-pairs shortest paths (APSP on small n) or repeated Dijkstra
Difficulty: Medium
Companies: Google, Amazon, Meta, Microsoft, IBM
Frequency: Medium
LeetCode: 1334

Weighted undirected graph n cities (0..n-1), edges from, to, weight. For distance threshold distanceThreshold, count how many other cities each city can reach with shortest-path distance <= threshold. Return the largest-index city among those with the minimum reachability count.

Recognition Cues

All-pairs shortest paths with tiny n (<= 100)
Floyd-Warshall O(n^3) is acceptable and simpler than n Dijkstras
Tie-break: maximum index wins

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

n × Dijkstra — O(n * (E log V)) — fine when sparse.
Floyd-Warshall — O(n^3) — tiny n — simplest to code under pressure.

Optimal Solution

Go

const inf = 1 << 30

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
	dist := make([][]int, n)
	for row := 0; row < n; row++ {
		dist[row] = make([]int, n)
		for col := 0; col < n; col++ {
			if row == col {
				dist[row][col] = 0
			} else {
				dist[row][col] = inf
			}
		}
	}
	for _, edge := range edges {
		from := edge[0]
		to := edge[1]
		weight := edge[2]
		if weight < dist[from][to] {
			dist[from][to] = weight
			dist[to][from] = weight
		}
	}
	for pivot := 0; pivot < n; pivot++ {
		for from := 0; from < n; from++ {
			for to := 0; to < n; to++ {
				if dist[from][pivot]+dist[pivot][to] < dist[from][to] {
					dist[from][to] = dist[from][pivot] + dist[pivot][to]
				}
			}
		}
	}
	bestCity := -1
	smallestReach := n + 1
	for city := 0; city < n; city++ {
		reachable := 0
		for other := 0; other < n; other++ {
			if city == other {
				continue
			}
			if dist[city][other] <= distanceThreshold {
				reachable++
			}
		}
		if reachable <= smallestReach {
			smallestReach = reachable
			bestCity = city
		}
	}
	return bestCity
}

JavaScript

const INF = 2 ** 30;

function findTheCity(n, edges, distanceThreshold) {
  const dist = Array.from({ length: n }, () => Array(n).fill(INF));
  for (let index = 0; index < n; index += 1) {
    dist[index][index] = 0;
  }
  for (const edge of edges) {
    const from = edge[0];
    const to = edge[1];
    const weight = edge[2];
    dist[from][to] = Math.min(dist[from][to], weight);
    dist[to][from] = Math.min(dist[to][from], weight);
  }
  for (let pivot = 0; pivot < n; pivot += 1) {
    for (let from = 0; from < n; from += 1) {
      for (let to = 0; to < n; to += 1) {
        if (dist[from][pivot] + dist[pivot][to] < dist[from][to]) {
          dist[from][to] = dist[from][pivot] + dist[pivot][to];
        }
      }
    }
  }
  let bestCity = -1;
  let smallestReach = n + 1;
  for (let city = 0; city < n; city += 1) {
    let reachable = 0;
    for (let other = 0; other < n; other += 1) {
      if (city === other) {
        continue;
      }
      if (dist[city][other] <= distanceThreshold) {
        reachable += 1;
      }
    }
    if (reachable <= smallestReach) {
      smallestReach = reachable;
      bestCity = city;
    }
  }
  return bestCity;
}

Walkthrough

Initialize pairwise distances; Floyd triple loop relaxes via each pivot. After APSP, scan each city counting neighbors within threshold; keep running min count; tie goes to larger city index due to <= update.

Invariant: After pivot loop ends, dist holds shortest path lengths for all pairs (no negative cycles here).

Edge Cases

Disconnected components — inf stays; counts ignore infinite pairs
Threshold 0 — only self loops matter; parallel edges still minimized by init
Multiple edges same endpoints — keep minimum weight in initialization

Pitfalls

Using strict < for tie on city index — problem wants largest city id among minima → use <= when updating best
Integer overflow on inf addition — use sufficiently large sentinel vs sum bounds

Variants

Directed graph — Floyd still applies with directed init.
Dynamic edge updates — Johnson or incremental APSP (advanced).
Return full distance matrix — already computed; reuse for multi-query thresholds.

Mind-Map Tags

#floyd-warshall #all-pairs-shortest-path #threshold-count #tie-break