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:

  1. Graph Representation: Create a 2D matrix g that acts as the adjacency matrix for the graph. The matrix g is initialized with inf (infinity) to indicate that initially, all distances between cities are unknown and considered infinitely large. Each edge from the edges array is then used to update the matrix with the actual distances, ensuring that the graph is bidirectional by setting g[f][t] = g[t][f] = w.

  2. Dijkstra's Shortest Path Algorithm: Define a nested function dijkstra(u) that calculates the shortest paths from city u 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 city u 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 distance dist[k].
    • Marks city k as visited vis[k] = True.
    • Updates the distances to its neighboring cities j if the current path through k offers a shorter distance than previously known dist[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 distances d in dist that are less than or equal to distanceThreshold.

  3. Finding the Optimal City: Once the graph is set and the dijkstra function is defined, iterate over each city from n-1 down to 0 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 the dijkstra function to find the number of reachable cities within the distanceThreshold and store this count in cnt.
    • Update the answer ans if cnt 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.

Finally, after the loop completes, the variable ans provides the desired city index as the result.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example 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:

  1. Graph Representation: We initialize a 2D matrix g as follows with inf 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 be 0 since the distance from a city to itself is 0, we update the corresponding entries.

  2. Dijkstra's Shortest Path Algorithm: For example, running dijkstra(0) starts by setting initial distances from city 0 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 of 4 from city 0:

    1From city 0: 2 cities (1 and 2) are reachable within the distance threshold of 4.

    We would similarly run dijkstra for cities 1, 2, and 3 to get their respective counts.

  3. Finding the Optimal City: We run the dijkstra function in reverse order from city 3 to 0 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 city 3. Since no other city has fewer reachable cities and we consider the largest city number in case of a tie, the answer would be city 3.

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 dimensions n x n, resulting in a space complexity of O(n^2).
  • The dist array, storing distances from the source vertex, and the vis array, indicating if a vertex has been visited, each take up O(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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄