1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
Problem Description
You are given n cities numbered from 0 to n-1 and a list of bidirectional weighted edges connecting these cities. Each edge is represented as [from, to, weight], where from and to are city numbers and weight is the distance between them.
Your task is to find the city that has the smallest number of reachable cities within a given distanceThreshold. A city is considered reachable from another city if there exists a path between them with total distance at most distanceThreshold.
Key requirements:
- Count how many cities are reachable from each city within the distance threshold
- Find the city with the minimum count of reachable cities
- If multiple cities have the same minimum count, return the city with the greatest number (highest index)
Example understanding:
- If city 2 can reach 3 other cities within the threshold distance, its count is 3
- If city 4 can reach 2 other cities within the threshold distance, its count is 2
- If both city 1 and city 3 have the minimum count of reachable cities, return 3 (the larger number)
The solution uses Dijkstra's algorithm to find shortest paths from each city to all other cities, then counts how many destinations are within the distance threshold. The algorithm iterates through cities in reverse order (from n-1 to 0) to ensure that when there's a tie in the minimum count, the city with the greatest number is selected.
Intuition
The core insight is that we need to find the shortest distances from each city to all other cities, then count how many cities fall within the distance threshold. This naturally points us toward a shortest path algorithm.
Why shortest paths? Because we want to know if a city is reachable within the threshold - and if there's any path within the threshold, the shortest path will definitely be within it. If the shortest path exceeds the threshold, then no valid path exists.
Since we need to perform this analysis for every city (to find which one has the minimum reachable cities), we essentially need an "all-pairs shortest path" solution. We have two main approaches:
-
Run single-source shortest path from each city - Use Dijkstra's algorithm
ntimes, once from each city as the source. This gives usO(n * n²) = O(n³)complexity with the basic implementation shown in the code. -
Use Floyd-Warshall algorithm - This directly computes all-pairs shortest paths in
O(n³)time.
The solution chooses Dijkstra's approach, where for each city i, we:
- Calculate shortest distances to all other cities using Dijkstra
- Count how many cities have distance
≤ distanceThreshold - Track the city with minimum count
A clever implementation detail: the code iterates through cities in reverse order (from n-1 to 0). This automatically handles the tie-breaking rule - when multiple cities have the same minimum count, we want the one with the greatest number. By processing in reverse and only updating when we find a strictly smaller count (t < cnt), we naturally keep the higher-numbered city in case of ties.
The graph is represented as an adjacency matrix g[i][j] storing edge weights, initialized with inf (infinity) for non-existent edges. This makes Dijkstra's implementation straightforward as we can directly access edge weights between any two cities.
Learn more about Graph, Dynamic Programming and Shortest Path patterns.
Solution Approach
The solution implements Dijkstra's algorithm to find shortest paths from each city, then counts reachable cities within the distance threshold.
Step 1: Build the Graph Representation
g = [[inf] * n for _ in range(n)]
for f, t, w in edges:
g[f][t] = g[t][f] = w
- Create an
n × nadjacency matrixginitialized withinf(infinity) - For each edge
[f, t, w], set bothg[f][t]andg[t][f]to weightw(bidirectional edges) - Using
inffor non-existent edges simplifies distance calculations
Step 2: Implement Dijkstra's Algorithm
The dijkstra(u) function finds shortest distances from city u to all other cities:
dist = [inf] * n dist[u] = 0 vis = [False] * n
- Initialize distances to all cities as
inf, except source cityuwhich is0 - Track visited cities with boolean array
vis
The core Dijkstra loop runs n iterations:
for _ in range(n):
k = -1
for j in range(n):
if not vis[j] and (k == -1 or dist[k] > dist[j]):
k = j
vis[k] = True
- Find the unvisited city
kwith minimum distance - Mark
kas visited
Then relax edges from the selected city:
for j in range(n):
if dist[k] + g[k][j] < dist[j]:
dist[j] = dist[k] + g[k][j]
- For each city
j, check if going throughkgives a shorter path - Update
dist[j]if a shorter path is found
Finally, count reachable cities:
return sum(d <= distanceThreshold for d in dist)
- Count how many cities have distance at most
distanceThreshold
Step 3: Find the Optimal City
ans, cnt = n, inf
for i in range(n - 1, -1, -1):
if (t := dijkstra(i)) < cnt:
cnt, ans = t, i
return ans
- Initialize
ans = n(invalid city) andcnt = inf(minimum count seen so far) - Iterate cities in reverse order from
n-1to0 - For each city
i, run Dijkstra to get counttof reachable cities - Update answer only if
t < cnt(strictly less than) - The reverse iteration ensures that for ties, we keep the city with greater number
Time Complexity: O(n³) - Running Dijkstra n times with O(n²) implementation
Space Complexity: O(n²) - For the adjacency matrix storage
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example with 4 cities and distanceThreshold = 4:
Input:
- Cities: 0, 1, 2, 3
- Edges:
[[0,1,3], [1,2,1], [1,3,4], [2,3,1]] - Distance threshold: 4
Step 1: Build the adjacency matrix
0 1 2 3 0 [inf, 3, inf, inf] 1 [ 3, inf, 1, 4 ] 2 [inf, 1, inf, 1 ] 3 [inf, 4, 1, inf ]
Step 2: Run Dijkstra from each city
From city 3:
- Initial: dist = [inf, inf, inf, 0], vis = [F, F, F, F]
- Iteration 1: Select city 3 (dist=0), mark visited, relax edges:
- dist[1] = min(inf, 0+4) = 4
- dist[2] = min(inf, 0+1) = 1
- Iteration 2: Select city 2 (dist=1), mark visited, relax edges:
- dist[1] = min(4, 1+1) = 2
- Iteration 3: Select city 1 (dist=2), mark visited, relax edges:
- dist[0] = min(inf, 2+3) = 5
- Final distances from city 3: [5, 2, 1, 0]
- Cities within threshold 4: cities 1, 2 → count = 2
From city 2:
- Run Dijkstra similarly
- Final distances: [4, 1, 0, 1]
- Cities within threshold 4: cities 0, 1, 3 → count = 3
From city 1:
- Final distances: [3, 0, 1, 2]
- Cities within threshold 4: cities 0, 2, 3 → count = 3
From city 0:
- Final distances: [0, 3, 4, 5]
- Cities within threshold 4: cities 1, 2 → count = 2
Step 3: Find the optimal city
Processing in reverse order (3 → 2 → 1 → 0):
- City 3: count = 2, update ans = 3, cnt = 2
- City 2: count = 3, no update (3 ≮ 2)
- City 1: count = 3, no update (3 ≮ 2)
- City 0: count = 2, no update (2 ≮ 2, equal counts but we keep city 3)
Result: City 3 has the minimum count of reachable cities (2). Since city 0 also has count 2, we return the one with the greater number, which is city 3.
Solution Implementation
1class Solution:
2 def findTheCity(
3 self, n: int, edges: List[List[int]], distanceThreshold: int
4 ) -> int:
5 def dijkstra(start_city: int) -> int:
6 """
7 Run Dijkstra's algorithm from start_city and count reachable cities
8 within the distance threshold.
9
10 Args:
11 start_city: The starting city for shortest path calculation
12
13 Returns:
14 Number of cities reachable within distanceThreshold
15 """
16 # Initialize distances to all cities as infinity
17 distances = [float('inf')] * n
18 distances[start_city] = 0
19
20 # Track visited cities
21 visited = [False] * n
22
23 # Process all cities
24 for _ in range(n):
25 # Find the unvisited city with minimum distance
26 min_dist_city = -1
27 for city in range(n):
28 if not visited[city] and (min_dist_city == -1 or distances[min_dist_city] > distances[city]):
29 min_dist_city = city
30
31 # Mark the selected city as visited
32 visited[min_dist_city] = True
33
34 # Update distances to neighboring cities through the selected city
35 for neighbor in range(n):
36 # Relaxation step: check if path through min_dist_city is shorter
37 if distances[min_dist_city] + adjacency_matrix[min_dist_city][neighbor] < distances[neighbor]:
38 distances[neighbor] = distances[min_dist_city] + adjacency_matrix[min_dist_city][neighbor]
39
40 # Count cities reachable within the distance threshold
41 return sum(dist <= distanceThreshold for dist in distances)
42
43 # Build adjacency matrix for the graph
44 adjacency_matrix = [[float('inf')] * n for _ in range(n)]
45 for from_city, to_city, weight in edges:
46 # Since the graph is undirected, set both directions
47 adjacency_matrix[from_city][to_city] = weight
48 adjacency_matrix[to_city][from_city] = weight
49
50 # Find the city with minimum reachable cities
51 result_city = n
52 min_reachable_count = float('inf')
53
54 # Iterate from highest numbered city to lowest (to handle ties)
55 for city in range(n - 1, -1, -1):
56 reachable_count = dijkstra(city)
57 if reachable_count < min_reachable_count:
58 min_reachable_count = reachable_count
59 result_city = city
60
61 return result_city
621class Solution {
2 // Class member variables
3 private int numCities;
4 private int[][] adjacencyMatrix;
5 private int[] distances;
6 private boolean[] visited;
7 private final int INFINITY = 1 << 30; // Large value representing infinity
8 private int maxDistance;
9
10 /**
11 * Find the city with the smallest number of reachable cities within distance threshold.
12 * If multiple cities have the same count, return the city with the greatest number.
13 *
14 * @param n Number of cities
15 * @param edges Array of edges where each edge is [from, to, weight]
16 * @param distanceThreshold Maximum distance to consider a city as reachable
17 * @return The city with smallest number of reachable cities
18 */
19 public int findTheCity(int n, int[][] edges, int distanceThreshold) {
20 // Initialize instance variables
21 this.numCities = n;
22 this.maxDistance = distanceThreshold;
23 adjacencyMatrix = new int[n][n];
24 distances = new int[n];
25 visited = new boolean[n];
26
27 // Initialize adjacency matrix with infinity values
28 for (int[] row : adjacencyMatrix) {
29 Arrays.fill(row, INFINITY);
30 }
31
32 // Build the undirected graph from edges
33 for (int[] edge : edges) {
34 int fromCity = edge[0];
35 int toCity = edge[1];
36 int weight = edge[2];
37 adjacencyMatrix[fromCity][toCity] = weight;
38 adjacencyMatrix[toCity][fromCity] = weight; // Undirected graph
39 }
40
41 // Find the city with minimum reachable cities
42 int resultCity = n;
43 int minReachableCities = INFINITY;
44
45 // Iterate from highest numbered city to lowest (to handle ties)
46 for (int currentCity = n - 1; currentCity >= 0; --currentCity) {
47 int reachableCount = dijkstra(currentCity);
48 if (reachableCount < minReachableCities) {
49 minReachableCities = reachableCount;
50 resultCity = currentCity;
51 }
52 }
53
54 return resultCity;
55 }
56
57 /**
58 * Apply Dijkstra's algorithm to find shortest paths from source city.
59 * Count how many cities are reachable within the distance threshold.
60 *
61 * @param sourceCity Starting city for Dijkstra's algorithm
62 * @return Number of cities reachable within distance threshold
63 */
64 private int dijkstra(int sourceCity) {
65 // Initialize distances and visited arrays
66 Arrays.fill(distances, INFINITY);
67 Arrays.fill(visited, false);
68 distances[sourceCity] = 0;
69
70 // Process all cities
71 for (int iteration = 0; iteration < numCities; ++iteration) {
72 // Find the unvisited city with minimum distance
73 int closestCity = -1;
74 for (int city = 0; city < numCities; ++city) {
75 if (!visited[city] &&
76 (closestCity == -1 || distances[closestCity] > distances[city])) {
77 closestCity = city;
78 }
79 }
80
81 // Mark the closest city as visited
82 visited[closestCity] = true;
83
84 // Update distances to all neighbors of the closest city
85 for (int neighbor = 0; neighbor < numCities; ++neighbor) {
86 distances[neighbor] = Math.min(
87 distances[neighbor],
88 distances[closestCity] + adjacencyMatrix[closestCity][neighbor]
89 );
90 }
91 }
92
93 // Count cities within the distance threshold
94 int reachableCityCount = 0;
95 for (int distance : distances) {
96 if (distance <= maxDistance) {
97 ++reachableCityCount;
98 }
99 }
100
101 return reachableCityCount;
102 }
103}
1041class Solution {
2public:
3 int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
4 // Initialize adjacency matrix with large values (representing no direct edge)
5 // Using 0x3f3f3f3f as infinity (a common trick in competitive programming)
6 int adjacencyMatrix[n][n];
7 memset(adjacencyMatrix, 0x3f, sizeof(adjacencyMatrix));
8
9 // Build the undirected weighted graph
10 for (auto& edge : edges) {
11 int from = edge[0];
12 int to = edge[1];
13 int weight = edge[2];
14 adjacencyMatrix[from][to] = weight;
15 adjacencyMatrix[to][from] = weight; // Undirected edge
16 }
17
18 // Lambda function to run Dijkstra's algorithm from a source city
19 auto dijkstra = [&](int source) -> int {
20 // Distance array to store shortest distances from source
21 int distance[n];
22 memset(distance, 0x3f, sizeof(distance));
23
24 // Visited array to track processed nodes
25 bool visited[n];
26 memset(visited, false, sizeof(visited));
27
28 // Distance from source to itself is 0
29 distance[source] = 0;
30
31 // Process all n nodes
32 for (int i = 0; i < n; ++i) {
33 // Find the unvisited node with minimum distance
34 int minNode = -1;
35 for (int j = 0; j < n; ++j) {
36 if (!visited[j] && (minNode == -1 || distance[j] < distance[minNode])) {
37 minNode = j;
38 }
39 }
40
41 // Mark the selected node as visited
42 visited[minNode] = true;
43
44 // Update distances to all neighbors of the selected node
45 for (int neighbor = 0; neighbor < n; ++neighbor) {
46 distance[neighbor] = min(distance[neighbor],
47 distance[minNode] + adjacencyMatrix[minNode][neighbor]);
48 }
49 }
50
51 // Count cities reachable within the distance threshold
52 return count_if(distance, distance + n,
53 [&](int dist) { return dist <= distanceThreshold; });
54 };
55
56 // Find the city with the smallest number of reachable cities
57 int resultCity = n;
58 int minReachableCities = n + 1; // Initialize with value larger than possible
59
60 // Iterate from largest city number to smallest (to handle ties)
61 for (int city = n - 1; city >= 0; --city) {
62 int reachableCities = dijkstra(city);
63
64 // Update result if we found a city with fewer reachable cities
65 if (reachableCities < minReachableCities) {
66 minReachableCities = reachableCities;
67 resultCity = city;
68 }
69 }
70
71 return resultCity;
72 }
73};
741/**
2 * Find the city with the smallest number of reachable cities within distance threshold.
3 * If there are multiple such cities, return the city with the greatest number.
4 *
5 * @param n - Number of cities (labeled from 0 to n-1)
6 * @param edges - Array of edges where each edge is [from, to, weight]
7 * @param distanceThreshold - Maximum distance to consider a city as reachable
8 * @returns The city number with the smallest number of reachable cities
9 */
10function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
11 // Initialize adjacency matrix with infinity for all distances
12 const adjacencyMatrix: number[][] = Array.from(
13 { length: n },
14 () => Array(n).fill(Infinity)
15 );
16
17 // Distance array for Dijkstra's algorithm
18 const distances: number[] = Array(n).fill(Infinity);
19
20 // Visited array to track processed nodes in Dijkstra's algorithm
21 const visited: boolean[] = Array(n).fill(false);
22
23 // Build the undirected graph from edges
24 for (const [fromCity, toCity, weight] of edges) {
25 adjacencyMatrix[fromCity][toCity] = weight;
26 adjacencyMatrix[toCity][fromCity] = weight;
27 }
28
29 /**
30 * Run Dijkstra's algorithm from a source city to find shortest paths to all other cities
31 *
32 * @param sourceCity - Starting city for shortest path calculation
33 * @returns Number of cities reachable within the distance threshold
34 */
35 const dijkstra = (sourceCity: number): number => {
36 // Reset arrays for new calculation
37 distances.fill(Infinity);
38 visited.fill(false);
39 distances[sourceCity] = 0;
40
41 // Process all n cities
42 for (let i = 0; i < n; ++i) {
43 // Find the unvisited city with minimum distance
44 let minDistanceCity = -1;
45 for (let j = 0; j < n; ++j) {
46 if (!visited[j] && (minDistanceCity === -1 || distances[j] < distances[minDistanceCity])) {
47 minDistanceCity = j;
48 }
49 }
50
51 // Mark the selected city as visited
52 visited[minDistanceCity] = true;
53
54 // Update distances to all neighbors through the selected city
55 for (let j = 0; j < n; ++j) {
56 distances[j] = Math.min(
57 distances[j],
58 distances[minDistanceCity] + adjacencyMatrix[minDistanceCity][j]
59 );
60 }
61 }
62
63 // Count cities within distance threshold (excluding source city itself)
64 return distances.filter(distance => distance <= distanceThreshold).length;
65 };
66
67 // Track the result city and minimum reachable count
68 let resultCity = n;
69 let minReachableCount = Infinity;
70
71 // Iterate from highest numbered city to lowest (to handle ties)
72 for (let currentCity = n - 1; currentCity >= 0; --currentCity) {
73 const reachableCount = dijkstra(currentCity);
74
75 // Update result if current city has fewer reachable cities
76 if (reachableCount < minReachableCount) {
77 minReachableCount = reachableCount;
78 resultCity = currentCity;
79 }
80 }
81
82 return resultCity;
83}
84Time and Space Complexity
Time Complexity: O(n³)
The algorithm uses Dijkstra's algorithm for each vertex to find the shortest paths. Breaking down the time complexity:
- The outer loop in the main function runs
ntimes (once for each city) - For each city, the
dijkstrafunction is called, which contains:- An outer loop that runs
ntimes - Inside this loop, there's a linear search to find the minimum unvisited vertex, taking
O(n)time - After finding the minimum vertex, it updates distances to all
nvertices, taking anotherO(n)time
- An outer loop that runs
- Therefore, each Dijkstra call takes
O(n²)time - With
ncalls to Dijkstra, the total time complexity isO(n) × O(n²) = O(n³)
Space Complexity: O(n²)
The space usage consists of:
- The adjacency matrix
gof sizen × n, which takesO(n²)space - Inside each Dijkstra call:
- The
distarray of sizentakesO(n)space - The
visarray of sizentakesO(n)space
- The
- Additional variables (
ans,cnt, loop variables) takeO(1)space
The dominant factor is the adjacency matrix, making the overall space complexity O(n²).
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Counting the Source City Itself
A critical pitfall is that Dijkstra's algorithm sets the distance from a city to itself as 0, which means dist[start_city] = 0. When counting reachable cities with sum(dist <= distanceThreshold for dist in distances), this includes the source city itself in the count.
Why it's a problem: The problem asks for "reachable cities from each city" which typically means OTHER cities, not including the city itself. Including the source city gives an incorrect count that's off by 1.
Solution:
# Incorrect: counts the source city itself
return sum(dist <= distanceThreshold for dist in distances)
# Correct: excludes the source city from the count
return sum(1 for i, dist in enumerate(distances)
if i != start_city and dist <= distanceThreshold)
2. Handling Tie-Breaking Incorrectly
When multiple cities have the same minimum count of reachable cities, the problem requires returning the city with the greatest number (highest index). A common mistake is iterating in forward order and using <= comparison.
Why it's a problem: Using forward iteration with <= would return the smallest numbered city in case of ties, not the largest.
Solution:
# Incorrect: forward iteration with <= gives wrong tie-breaking
for city in range(n):
reachable_count = dijkstra(city)
if reachable_count <= min_reachable_count: # Wrong!
min_reachable_count = reachable_count
result_city = city
# Correct: reverse iteration with strict < comparison
for city in range(n - 1, -1, -1):
reachable_count = dijkstra(city)
if reachable_count < min_reachable_count: # Strict less than
min_reachable_count = reachable_count
result_city = city
3. Not Handling Disconnected Cities
If a city is not connected to another city through any path, the distance remains inf. This is handled correctly in the code, but a pitfall would be not initializing distances properly.
Why it's a problem: Without proper infinity initialization, unreachable cities might be incorrectly counted as reachable.
Solution:
Always initialize the adjacency matrix and distance arrays with float('inf') for non-existent connections, ensuring disconnected cities are never counted as reachable.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph
Want a Structured Path to Master System Design Too? Don’t Miss This!