Editorial
Core insight
Find the City With the Smallest Number of Neighbors at a Threshold Distance · Graph Traversal Patterns (DFS & BFS)
Core Insight for Find the City With the Smallest Number of Neighbors at a Threshold Distance
The key to solving LeetCode 1334 is recognizing that we need the shortest path from every node to every other node. Since the edges have weights, a standard BFS (which assumes unit weights) is insufficient. We need a weighted traversal.
The "Deep Copy / Cloning" subpattern manifests here in the independence of the search: To find the answer for City 0, we run a traversal. To find the answer for City 1, we must "reset" our view of the world—effectively cloning the initial conditions—and run the traversal again. We cannot reuse the visitation state of City 0 for City 1 because the distances are relative to the source.
We can implement this using Dijkstra’s Algorithm (a weighted variation of BFS).
Visual Description: Imagine the graph as a network of pipes with different lengths.
- Instantiation 0: We inject water at City 0. The water flows outwards. We stop the flow along any pipe once the total distance travels exceeds
distanceThreshold. We count how many cities get wet. - Instantiation 1: We "clone" the graph setup (resetting all wet/dry statuses) and inject water at City 1. We count the wet cities again.
- We repeat this process for all
ncities.
The algorithm maintains the invariant that for a specific source city, we always expand the path with the smallest cumulative weight first (using a Priority Queue). This guarantees that the first time we reach a neighbor, it is via the shortest possible path.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance Solution & Explanation
Problem Overview
TL;DR: Run a weighted graph traversal (Dijkstra's Algorithm) from each city to count how many neighbors are reachable within the distance threshold, then return the city with the lowest count (tie-breaking with the highest city ID).
In the problem "Find the City With the Smallest Number of Neighbors at a Threshold Distance," we are given n cities and a list of weighted edges connecting them. We are also given a distanceThreshold. For every city, we must determine how many other cities can be reached such that the total path weight does not exceed the threshold. Our goal is to identify the city that has the fewest such reachable neighbors. If multiple cities share the same minimum number of neighbors, we return the one with the largest numerical label.
This is a popular interview question because it combines graph construction with the requirement to run shortest-path logic multiple times.
Brute Force Approach for Find the City With the Smallest Number of Neighbors at a Threshold Distance
A naive brute force approach might involve attempting to find all simple paths from every node to every other node using a recursive Depth First Search (DFS).
- Start a DFS from City
i. - Traverse all connected edges, accumulating the distance.
- If the accumulated distance exceeds
distanceThreshold, stop that branch. - Track unique visited nodes for the current source City
i. - Repeat for all
ncities.
Pseudo-code:
function solveNaive(n, edges, limit):
minNeighbors = infinity
resultCity = -1
for i from 0 to n-1:
count = 0
for j from 0 to n-1:
if i == j: continue
# Naive recursion to check reachability
if hasPathUnderThreshold(i, j, limit, visited):
count++
if count <= minNeighbors:
minNeighbors = count
resultCity = i
return resultCityWhy it fails:
The time complexity of finding all paths in a graph is exponential in the worst case. A naive DFS does not efficiently handle cycles or intersecting paths and re-calculates the same sub-paths repeatedly. With n up to 100, an exponential solution will immediately trigger a Time Limit Exceeded (TLE) error. Furthermore, simple DFS does not guarantee finding the shortest path first, making it difficult to correctly validate the threshold in weighted graphs.
Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)
We will use Dijkstra's Algorithm iteratively for each node.
- Graph Representation: Convert the
edgesinput into an Adjacency List (e.g.,List<List<int[]>>orvector<vector<pair>>) for efficient traversal. - Iterative Traversal: Loop through every city
ifrom0ton-1. - The "Cloned" Search: Inside the loop, initialize a Dijkstra search rooted at
i.- Maintain a
distarray initialized to infinity, withdist[i] = 0. - Use a Min-Heap (Priority Queue) to select the closest reachable node.
- Expand nodes: For current node
u, check all neighborsv. Ifdist[u] + weight < dist[v], updatedist[v]and push to the heap.
- Maintain a
- Threshold Check: After the Dijkstra traversal for city
icompletes (or during the process), count how many citiesjhavedist[j] <= distanceThreshold. - Result Update:
- Keep track of
minReachableCountandbestCity. - If the current city
ihas fewer reachable neighbors thanminReachableCount, update the record. - Crucial Tie-Breaker: If city
ihas the same number of neighbors asminReachableCount, updatebestCity = i. Since we iterate from 0 ton-1, this naturally keeps the city with the greatest ID.
- Keep track of
Execution Flow
Let's assume n=4 and we are processing City 0.
- Initialize:
minReachable = infinity,res = -1. - Start Loop:
source = 0. - Setup Traversal:
distarray:[0, inf, inf, inf]- Priority Queue (PQ):
[(0, Node 0)](distance, node)
- Process PQ:
- Pop
(0, 0). Neighbors of 0 are checked. - Push neighbors to PQ if the new distance is better and within threshold logic.
- Update
distarray accordingly.
- Pop
- Count: After PQ is empty, scan
dist. Suppose City 0 can reach 2 other cities within the threshold. - Update Global State:
minReachablebecomes 2,resbecomes 0. - Next Iteration:
source = 1.- Reset: Create a fresh
distarray (conceptually "cloning" the search space). - Run Dijkstra from City 1.
- Suppose City 1 reaches 3 cities. 3 > 2, so ignore.
- Reset: Create a fresh
- Next Iteration:
source = 3.- Run Dijkstra. Suppose City 3 reaches 2 cities.
- Since 2 ==
minReachable, we updateres = 3(because 3 > 0).
- Finish: Return
res.
Proof of Correctness
The correctness relies on the properties of Dijkstra's Algorithm and the exhaustive search pattern.
- Shortest Path Guarantee: Dijkstra's algorithm is proven to find the shortest path in a graph with non-negative edge weights. This ensures we accurately determine if a city is within
distanceThreshold. - Independence: By running the algorithm separately for each node, we respect the directed/weighted nature of paths from specific sources.
- Completeness: Iterating through all
nnodes ensures we evaluate the candidate set completely. The tie-breaking condition is explicitly handled by the comparison logic.
Pattern Reuse Notes
The Graph Traversal pattern and the concept of Cloning/Replicating logic appear in these related problems:
- LeetCode 133: Clone Graph - Requires traversing a graph to create a literal deep copy of the structure.
- LeetCode 138: Copy List with Random Pointer - Involves traversing a linked list and mapping original nodes to cloned nodes.
- LeetCode 1490: Clone N-ary Tree - Uses DFS/BFS to replicate a tree structure.
In LeetCode 1334, we "clone" the traversal instance rather than the data structure itself, but the underlying traversal mechanics (DFS/BFS) remain the shared foundation.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 1334
1#include <vector>
2#include <queue>
3#include <climits>
4
5using namespace std;
6
7class Solution {
8public:
9 int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
10 // Build Adjacency List
11 // pattern: Graph Traversal
12 vector<vector<pair<int, int>>> adj(n);
13 for (const auto& edge : edges) {
14 adj[edge[0]].push_back({edge[1], edge[2]});
15 adj[edge[1]].push_back({edge[0], edge[2]});
16 }
17
18 int minReachable = n; // Max possible is n-1, so n is safe infinity
19 int bestCity = -1;
20
21 // Run Dijkstra for each city (Cloning the traversal logic)
22 for (int i = 0; i < n; ++i) {
23 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
24 vector<int> dist(n, INT_MAX);
25
26 dist[i] = 0;
27 pq.push({0, i});
28
29 int reachableCount = 0;
30
31 while (!pq.empty()) {
32 int d = pq.top().first;
33 int u = pq.top().second;
34 pq.pop();
35
36 if (d > dist[u]) continue;
37
38 for (auto& neighbor : adj[u]) {
39 int v = neighbor.first;
40 int weight = neighbor.second;
41
42 if (dist[u] + weight < dist[v]) {
43 dist[v] = dist[u] + weight;
44 pq.push({dist[v], v});
45 }
46 }
47 }
48
49 // Count reachable cities within threshold
50 for (int j = 0; j < n; ++j) {
51 if (i != j && dist[j] <= distanceThreshold) {
52 reachableCount++;
53 }
54 }
55
56 // Update result based on problem constraints
57 // We want smallest count. If equal, we want greater ID (i).
58 if (reachableCount <= minReachable) {
59 minReachable = reachableCount;
60 bestCity = i;
61 }
62 }
63
64 return bestCity;
65 }
66};Java Solution for LeetCode 1334
1import java.util.*;
2
3class Solution {
4 public int findTheCity(int n, int[][] edges, int distanceThreshold) {
5 // Graph Construction
6 List<List<int[]>> adj = new ArrayList<>();
7 for (int i = 0; i < n; i++) {
8 adj.add(new ArrayList<>());
9 }
10 for (int[] edge : edges) {
11 adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
12 adj.get(edge[1]).add(new int[]{edge[0], edge[2]});
13 }
14
15 int minReachable = n;
16 int bestCity = -1;
17
18 // Iterate through every city to run a fresh traversal
19 for (int i = 0; i < n; i++) {
20 int reachableCount = dijkstra(n, adj, i, distanceThreshold);
21
22 // If count is smaller or equal (since we iterate 0->n-1,
23 // equal updates to the larger index automatically)
24 if (reachableCount <= minReachable) {
25 minReachable = reachableCount;
26 bestCity = i;
27 }
28 }
29
30 return bestCity;
31 }
32
33 private int dijkstra(int n, List<List<int[]>> adj, int source, int threshold) {
34 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
35 int[] dist = new int[n];
36 Arrays.fill(dist, Integer.MAX_VALUE);
37
38 dist[source] = 0;
39 pq.offer(new int[]{0, source}); // {distance, node}
40
41 while (!pq.isEmpty()) {
42 int[] curr = pq.poll();
43 int d = curr[0];
44 int u = curr[1];
45
46 if (d > dist[u]) continue;
47
48 for (int[] neighbor : adj.get(u)) {
49 int v = neighbor[0];
50 int weight = neighbor[1];
51
52 if (dist[u] + weight < dist[v]) {
53 dist[v] = dist[u] + weight;
54 pq.offer(new int[]{dist[v], v});
55 }
56 }
57 }
58
59 int count = 0;
60 for (int j = 0; j < n; j++) {
61 if (source != j && dist[j] <= threshold) {
62 count++;
63 }
64 }
65 return count;
66 }
67}Python Solution for LeetCode 1334
1import heapq
2
3class Solution:
4 def findTheCity(self, n: int, edges: list[list[int]], distanceThreshold: int) -> int:
5 # Build adjacency list
6 adj = [[] for _ in range(n)]
7 for u, v, w in edges:
8 adj[u].append((v, w))
9 adj[v].append((u, w))
10
11 min_reachable = float('inf')
12 best_city = -1
13
14 # Run Dijkstra for each city
15 for i in range(n):
16 # Priority queue stores (current_dist, node)
17 pq = [(0, i)]
18 dist = [float('inf')] * n
19 dist[i] = 0
20
21 while pq:
22 d, u = heapq.heappop(pq)
23
24 if d > dist[u]:
25 continue
26
27 for v, w in adj[u]:
28 if dist[u] + w < dist[v]:
29 dist[v] = dist[u] + w
30 heapq.heappush(pq, (dist[v], v))
31
32 # Count valid neighbors
33 count = 0
34 for j in range(n):
35 if i != j and dist[j] <= distanceThreshold:
36 count += 1
37
38 # Update result:
39 # If we find a smaller count, update.
40 # If we find an equal count, update (since we want the larger ID).
41 if count <= min_reachable:
42 min_reachable = count
43 best_city = i
44
45 return best_city