1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
Problem Description
In this problem, we are given a network of cities, connected by roads with certain weights indicating the distance between them. There are n
cities, and each city is uniquely numbered from 0
to n-1
. The network is represented by an array edges
, where each element edges[i]
contains three integers [from_i, to_i, weight_i]
that define a bidirectional road with a certain distance (or weight) between city from_i
and city to_i
. Additionally, we are given an integer distanceThreshold
that represents a distance limit.
Our goal is to find the city that has the smallest number of cities within the reachable distance threshold. Specifically, this means we want the city from which the number of other cities that can be reached through any path, without exceeding the distanceThreshold
, is minimized. If there are multiple cities meeting this criteria, we should return the city with the greatest number to break the tie.
This is essentially a graph problem, where we are asked to calculate the reachability of each city within the given distance constraint and then select the optimal city accordingly.
Intuition
To solve this problem, we can apply the following process:
- Use a graph representation to model the cities and roads, considering the roads as edges and the cities as nodes of the graph.
- For each city, determine the shortest path distances to all other cities, which can be done using Dijkstra's algorithm, an algorithm well-known for finding the shortest paths in a graph with non-negative weights.
- Since the question involves bidirectional edges and all weights are non-negative, Dijkstra's algorithm is an appropriate choice for this task.
- To calculate the connectivity of each city, we count the number of cities that can be reached from it without exceeding the
distanceThreshold
. This count is obtained by measuring the distance of the shortest path to every other city and checking if it falls within the threshold. - Finally, iterate through all cities in reverse order, using each city as a source to run Dijkstra's algorithm. We do this in reverse to handle the tie-breaking condition that asks for the city with the greatest number if there are multiple answers.
- Keep track of the city with the minimum number of reachable cities within the
distanceThreshold
. When a city with fewer reachable cities is found, update the answer.
The Python code implements these steps by first creating a graph representation g
, where g[u][v]
contains the weight of the edge (distance) between cities u
and v
, initializing all distances to infinity to indicate no initial connection. It then performs Dijkstra's algorithm for each city to find the reachable cities, counting them as per the above rules, and returns the optimal city's index.
Learn more about Graph, Dynamic Programming and Shortest Path patterns.
Solution Approach
The solution approach involves implementing Dijkstra's shortest path algorithm and using a 2D matrix to represent the graph. The following steps outline the algorithm and use of data structures:
-
Graph Representation: Create a 2D matrix
g
that acts as the adjacency matrix for the graph. The matrixg
is initialized withinf
(infinity) to indicate that initially, all distances between cities are unknown and considered infinitely large. Each edge from theedges
array is then used to update the matrix with the actual distances, ensuring that the graph is bidirectional by settingg[f][t] = g[t][f] = w
. -
Dijkstra's Shortest Path Algorithm: Define a nested function
dijkstra(u)
that calculates the shortest paths from cityu
to all other cities in the graph using Dijkstra's algorithm. The algorithm maintains the following:- An array
dist
that holds the shortest distance from the source cityu
to every other city. - A boolean array
vis
to keep track of which cities have been visited and processed.
Dijkstra's algorithm then operates in
n
iterations, where in each iteration it:- Finds the unvisited city
k
with the smallest distancedist[k]
. - Marks city
k
as visitedvis[k] = True
. - Updates the distances to its neighboring cities
j
if the current path throughk
offers a shorter distance than previously knowndist[j] = min(dist[j], dist[k] + g[k][j])
.
After running the algorithm, a count of cities reachable within
distanceThreshold
is returned by summing up all distancesd
indist
that are less than or equal todistanceThreshold
. - An array
-
Finding the Optimal City: Once the graph is set and the
dijkstra
function is defined, iterate over each city fromn-1
down to0
to perform Dijkstra's algorithm and count the reachable cities. This backward iteration is performed to easily handle the condition of returning the city with the greatest number in case of a tie.- For each city
i
, use thedijkstra
function to find the number of reachable cities within thedistanceThreshold
and store this count incnt
. - Update the answer
ans
ifcnt
is less than the smallest number of reachable cities encountered so far,t
. This condition also ensures the correct city is returned in case of a tie by checking cities in reverse order.
- For each city
Finally, after the loop completes, the variable ans
provides the desired city index as the result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Suppose we are given a network of cities with the following connections and a distanceThreshold
of 4:
- There are
n = 4
cities:0, 1, 2, 3
. - The
edges
array is given as[[0, 1, 3], [1, 2, 1], [2, 3, 1], [0, 3, 5]]
.
This describes a network where city 0
is connected to city 1
with a distance of 3
, city 1
to city 2
with a distance of 1
, city 2
to city 3
with a distance of 1
, and city 0
to city 3
with a distance of 5
.
Now, let's walk through the solution approach using this example:
-
Graph Representation: We initialize a 2D matrix
g
as follows withinf
values:1g = [ 2 [inf, inf, inf, inf], 3 [inf, inf, inf, inf], 4 [inf, inf, inf, inf], 5 [inf, inf, inf, inf] 6]
We update the matrix
g
with the given distances:1g = [ 2 [inf, 3, inf, 5], 3 [ 3, inf, 1, inf], 4 [inf, 1, inf, 1], 5 [ 5, inf, 1, inf] 6]
Noting that
g[i][i]
should be0
since the distance from a city to itself is0
, we update the corresponding entries. -
Dijkstra's Shortest Path Algorithm: For example, running
dijkstra(0)
starts by setting initial distances from city0
to others:1dist = [0, 3, inf, 5] 2vis = [False, False, False, False]
Iterating through the algorithm, we update distances and the visited array as we find shorter paths:
1After visiting city 1: 2dist = [0, 3, 4, 5] 3vis = [True, True, False, False] 4 5After visiting city 2 (update distances to neighbors): 6dist = [0, 3, 4, 5] 7vis = [True, True, True, False] 8 9After visiting city 3: 10No updates, since all other cities are either visited or have shorter distances via other paths.
We count the number of cities within the
distanceThreshold
of4
from city0
:1From city 0: 2 cities (1 and 2) are reachable within the distance threshold of 4.
We would similarly run
dijkstra
for cities1
,2
, and3
to get their respective counts. -
Finding the Optimal City: We run the
dijkstra
function in reverse order from city3
to0
and maintain a count of reachable cities for each.Suppose after running we find counts as follows:
1From city 3: 1 city reachable (city 2). 2From city 2: 2 cities reachable (cities 1 and 3). 3From city 1: 2 cities reachable (cities 0 and 2). 4From city 0: 2 cities reachable (cities 1 and 2).
We consider the smallest number of reachable cities, which is
1
for city3
. Since no other city has fewer reachable cities and we consider the largest city number in case of a tie, the answer would be city3
.
In conclusion, for our given example with distanceThreshold
of 4
, the optimal city is 3
, because it has the smallest number of reachable cities within the distance threshold. If there had been another city with the same number of reachable cities, we would have chosen the one with the greatest number, as per the problem requirements.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findTheCity(self, n: int, edges: List[List[int]], distance_threshold: int) -> int:
5 # Function to perform Dijkstra's algorithm to find the shortest
6 # paths from node `u` to all other nodes in the graph.
7 def dijkstra(u: int) -> int:
8 # Initialize distances from `u` to all nodes as infinity.
9 distances = [float('inf')] * n
10 # Distance to the source node itself is 0.
11 distances[u] = 0
12 # Keep a visited array to track nodes that have been processed.
13 visited = [False] * n
14
15 # Repeat the process for all nodes.
16 for _ in range(n):
17 # `k` is going to be the unvisited node with the smallest distance.
18 k = -1
19 for j in range(n):
20 # Select the unvisited node with the smallest distance.
21 if not visited[j] and (k == -1 or distances[k] > distances[j]):
22 k = j
23 # Mark the selected node as visited.
24 visited[k] = True
25 # Update the distances to all nodes from `k`.
26 for j in range(n):
27 distances[j] = min(distances[j], distances[k] + graph[k][j])
28
29 # Return the number of nodes within the distance_threshold from `u`.
30 return sum(d <= distance_threshold for d in distances)
31
32 # Create a graph representation (adjacency matrix) with distances set to infinity.
33 graph = [[float('inf')] * n for _ in range(n)]
34 # Set the distance for all the edges provided in the input.
35 for start, end, weight in edges:
36 graph[start][end] = graph[end][start] = weight
37
38 # `res_city` is going to be the resultant city with the smallest number
39 # of reachable cities (within threshold) when tied with another city.
40 res_city = n
41 # `min_reachable_cities` keeps track of the smallest number of reachable cities found.
42 min_reachable_cities = float('inf')
43
44 # Iterate over all cities in reverse order to account for the smallest numbered city in a tie.
45 for i in range(n - 1, -1, -1):
46 # Get the number of cities reachable from city `i` within the distance threshold.
47 reachable_cities = dijkstra(i)
48 # If the number of reachable cities is less than the current minimum,
49 # update `min_reachable_cities` and `res_city`.
50 if reachable_cities < min_reachable_cities:
51 min_reachable_cities = reachable_cities
52 res_city = i
53
54 # Return the city with the smallest number of reachable cities or the smallest
55 # numbered city in case of a tie.
56 return res_city
57
1import java.util.Arrays;
2
3public class Solution {
4 private int numCities;
5 private int[][] graph;
6 private int[] distances;
7 private boolean[] visited;
8 private final int INF = 1 << 30;
9 private int distanceThreshold;
10
11 public int findTheCity(int numCities, int[][] edges, int distanceThreshold) {
12 this.numCities = numCities;
13 this.distanceThreshold = distanceThreshold;
14 graph = new int[numCities][numCities];
15 distances = new int[numCities];
16 visited = new boolean[numCities];
17
18 // Initialize the graph with INF values to indicate no direct path
19 for (int[] row : graph) {
20 Arrays.fill(row, INF);
21 }
22
23 // Set the path weights for the given edges in both directions
24 for (int[] edge : edges) {
25 int from = edge[0], to = edge[1], weight = edge[2];
26 graph[from][to] = weight;
27 graph[to][from] = weight;
28 }
29
30 int cityWithLeastReachableCities = numCities, minReachableCities = INF;
31
32 // Iterate over each city to find the one with the minimum reachable cities within threshold
33 for (int city = numCities - 1; city >= 0; --city) {
34 int reachableCities = dijkstra(city);
35 if (minReachableCities >= reachableCities) { // Use '>=' to get the smallest indexed city in case of a tie
36 minReachableCities = reachableCities;
37 cityWithLeastReachableCities = city;
38 }
39 }
40 return cityWithLeastReachableCities;
41 }
42
43 private int dijkstra(int startCity) {
44 Arrays.fill(distances, INF);
45 Arrays.fill(visited, false);
46 distances[startCity] = 0;
47
48 for (int i = 0; i < numCities; ++i) {
49 int closest = -1;
50
51 // Find the unvisited city with the smallest known distance
52 for (int j = 0; j < numCities; ++j) {
53 if (!visited[j] && (closest == -1 || distances[closest] > distances[j])) {
54 closest = j;
55 }
56 }
57
58 visited[closest] = true;
59
60 // Update distances of neighboring cities
61 for (int j = 0; j < numCities; ++j) {
62 distances[j] = Math.min(distances[j], distances[closest] + graph[closest][j]);
63 }
64 }
65
66 int countWithinThreshold = 0;
67
68 // Count how many cities are within the threshold distance
69 for (int distance : distances) {
70 if (distance <= distanceThreshold) {
71 countWithinThreshold++;
72 }
73 }
74 return countWithinThreshold;
75 }
76}
77
1class Solution {
2public:
3 int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
4 const int INF = 1e7; // A constant representing an "infinite" distance
5 vector<vector<int>> graph(n, vector<int>(n, INF));
6 // Initialize distances and visited flags for Dijkstra's algorithm
7 vector<int> distances(n, INF);
8 vector<bool> visited(n);
9
10 // Building the graph with bidirectional edges and their weights
11 for (auto& edge : edges) {
12 int from = edge[0], to = edge[1], weight = edge[2];
13 graph[from][to] = graph[to][from] = weight;
14 }
15
16 // Lambda function to perform Dijkstra's algorithm from a given node
17 auto dijkstra = [&](int startNode) {
18 distances.assign(n, INF);
19 visited.assign(n, false);
20 distances[startNode] = 0;
21
22 // Find shortest paths from startNode to all other nodes
23 for (int i = 0; i < n; ++i) {
24 int closestNode = -1;
25 for (int j = 0; j < n; ++j) {
26 if (!visited[j] && (closestNode == -1 || distances[j] < distances[closestNode])) {
27 closestNode = j;
28 }
29 }
30 visited[closestNode] = true;
31 for (int neighbourIndex = 0; neighbourIndex < n; ++neighbourIndex) {
32 distances[neighbourIndex] = min(distances[neighbourIndex], distances[closestNode] + graph[closestNode][neighbourIndex]);
33 }
34 }
35
36 // Count the number of nodes that are within the distance threshold
37 int countWithinThreshold = 0;
38 for (int& distance : distances) {
39 countWithinThreshold += distance <= distanceThreshold;
40 }
41 return countWithinThreshold;
42 };
43
44 int bestCity = 0, minReachableCities = INF;
45 // Reverse iteration to find the city with the smallest number of reachable cities
46 for (int cityIndex = n - 1; cityIndex >= 0; --cityIndex) {
47 int reachableCities = dijkstra(cityIndex);
48 // If the current city has fewer or equal reachable cities, update bestCity
49 if (minReachableCities >= reachableCities) {
50 minReachableCities = reachableCities;
51 bestCity = cityIndex;
52 }
53 }
54 return bestCity;
55 }
56};
57
1// Constant representing an "infinite" distance
2const INF = 1e7;
3let graph: number[][];
4let distances: number[];
5let visited: boolean[];
6
7// Function to build the graph with bidirectional edges and their weights
8function buildGraph(edges: number[][], n: number): void {
9 graph = Array.from({ length: n }, () => Array(n).fill(INF));
10
11 edges.forEach(edge => {
12 const [from, to, weight] = edge;
13 graph[from][to] = weight;
14 graph[to][from] = weight;
15 });
16}
17
18// Function to perform Dijkstra's algorithm from a given node
19function dijkstra(startNode: number, n: number, distanceThreshold: number): number {
20 distances = Array(n).fill(INF);
21 visited = Array(n).fill(false);
22 distances[startNode] = 0;
23
24 for (let i = 0; i < n; ++i) {
25 let closestNode = -1;
26
27 for (let j = 0; j < n; ++j) {
28 if (!visited[j] && (closestNode === -1 || distances[j] < distances[closestNode])) {
29 closestNode = j;
30 }
31 }
32
33 visited[closestNode] = true;
34
35 for (let neighbourIndex = 0; neighbourIndex < n; ++neighbourIndex) {
36 if (distances[neighbourIndex] > distances[closestNode] + graph[closestNode][neighbourIndex]) {
37 distances[neighbourIndex] = distances[closestNode] + graph[closestNode][neighbourIndex];
38 }
39 }
40 }
41
42 // Counting the number of nodes that are within the distance threshold
43 return distances.filter(distance => distance <= distanceThreshold).length;
44}
45
46// Function to find the city with the minimum number of reachable cities within a given threshold
47function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
48 buildGraph(edges, n);
49
50 let bestCity = 0;
51 let minReachableCities = INF;
52
53 // Reverse iteration to find the city with the smallest number of reachable cities
54 for (let cityIndex = n - 1; cityIndex >= 0; --cityIndex) {
55 const reachableCities = dijkstra(cityIndex, n, distanceThreshold);
56
57 // Update bestCity if the current city has a smaller or equal number of reachable cities
58 if (minReachableCities >= reachableCities) {
59 minReachableCities = reachableCities;
60 bestCity = cityIndex;
61 }
62 }
63
64 return bestCity;
65}
66// Usage:
67// findTheCity(numberOfCities, edgeList, distanceThreshold);
68
Time and Space Complexity
The given solution implements Dijkstra's algorithm without a priority queue to find the number of cities within a certain distance threshold from each city. The time complexity and space complexity of the provided code are as follows:
Time Complexity
The time complexity of standard Dijkstra's algorithm using a priority queue is O(E + V log V)
, where E
is the number of edges, and V
is the number of vertices (or nodes). However, this implementation uses a simpler version without a priority queue and utilizes two nested loops instead.
There's an outer loop to apply Dijkstra's algorithm on each vertex, which runs n
times, where n
is the number of nodes:
- The inner loop to find the unvisited node with the smallest distance runs
n
times. - The second inner loop to update the distances of adjacent nodes runs
n
times.
Consequently, the Dijkstra's algorithm part has a time complexity of O(n^2)
. Since we are running this for each node, the overall time complexity is O(n^3)
.
Space Complexity
The space complexity of the code is due to the storage of the graph and the arrays used during Dijkstra's algorithm execution:
- The graph
g
is represented as a 2D array (adjacency matrix) with dimensionsn x n
, resulting in a space complexity ofO(n^2)
. - The
dist
array, storing distances from the source vertex, and thevis
array, indicating if a vertex has been visited, each take upO(n)
space.
Hence, the total space complexity of the algorithm is O(n^2)
, which is dominated by the space taken up by the adjacency matrix.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
https algomonster s3 us east 2 amazonaws com 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
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
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.