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

Med

#1240Time: O(n * (E + n) log n). We run Dijkstra's algorithm `n` times. Each run of Dijkstra's with a binary heap has a complexity of `O((E+n) log n)`. For a dense graph, this approaches `O(n^3 log n)`.Space: O(n + E), where `n` is the number of cities and `E` is the number of edges. This is for storing the adjacency list. In the worst case, `E` can be `O(n^2)`, making the space complexity `O(n^2)`.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between cities from_i and to_i, and given the integer distanceThreshold.

Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.

Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2:

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i, distanceThreshold <= 10^4
All pairs (from_i, to_i) are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach tackles the problem by running a single-source shortest path (SSSP) algorithm from every city. Since all edge weights are positive, Dijkstra's algorithm is a perfect fit. By executing Dijkstra's n times, once for each city as the source, we can determine the shortest distance from every city to every other city. After obtaining these distances for a given source city, we count how many other cities are within the distanceThreshold and update our answer accordingly.

Algorithm

Graph Representation: First, build an adjacency list to represent the graph. For each edge [u, v, w], add (v, w) to u's list and (u, w) to v's list since the graph is bidirectional.
Iterate Through Cities: Loop through each city i from 0 to n-1, treating each one as a potential starting node.
Run Dijkstra's Algorithm: For each city i, run Dijkstra's algorithm to find the shortest path from i to all other cities. Use a priority queue to efficiently manage nodes to visit.
- Initialize a dist array with infinity for all nodes, and dist[i] = 0.
- Push {0, i} (distance, node) to the priority queue.
- While the priority queue is not empty, extract the node u with the smallest distance and relax its edges, updating distances for its neighbors v if a shorter path dist[u] + weight(u,v) is found.
Count Reachable Neighbors: After Dijkstra's completes for city i, iterate through all cities j from 0 to n-1. Count how many cities j (where j != i) have dist[j] <= distanceThreshold.
Find the Best City: Keep track of the city with the minimum number of reachable neighbors found so far. Let this be min_count and the city be result_city.
- If the current city's neighbor count is less than or equal to min_count, update min_count with the new count and result_city to i. The <= condition ensures that in case of a tie, the city with the larger index is chosen (as we iterate i from 0 to n-1).
Return Result: After checking all n cities, result_city will hold the answer.

Walkthrough

To implement this, we first construct an adjacency list representation of the graph from the input edges. Then, we loop through each city i from 0 to n-1. In each iteration, we use city i as the source and apply Dijkstra's algorithm. Dijkstra's uses a priority queue to always explore the node with the currently shortest known distance from the source, guaranteeing that we find the shortest paths in a greedy manner. Once the shortest distances from i to all other nodes are computed, we count how many of these distances are within the given distanceThreshold. We maintain a variable for the minimum count found so far and the corresponding city. If a city has a smaller count, or an equal count but a larger index, it becomes our new candidate for the answer. This process is repeated for all n cities to find the global best city.

1import java.util.*;2 3class Solution {4    public int findTheCity(int n, int[][] edges, int distanceThreshold) {5        List<List<int[]>> adj = new ArrayList<>();6        for (int i = 0; i < n; i++) {7            adj.add(new ArrayList<>());8        }9        for (int[] edge : edges) {10            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});11            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});12        }13 14        int minReachableCities = n;15        int resultCity = -1;16 17        for (int i = 0; i < n; i++) {18            int[] dist = dijkstra(n, adj, i);19            int reachableCount = 0;20            for (int j = 0; j < n; j++) {21                if (i != j && dist[j] <= distanceThreshold) {22                    reachableCount++;23                }24            }25 26            if (reachableCount <= minReachableCities) {27                minReachableCities = reachableCount;28                resultCity = i;29            }30        }31        return resultCity;32    }33 34    private int[] dijkstra(int n, List<List<int[]>> adj, int startNode) {35        int[] dist = new int[n];36        Arrays.fill(dist, Integer.MAX_VALUE);37        dist[startNode] = 0;38 39        // PriorityQueue stores {distance, node}40        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));41        pq.offer(new int[]{0, startNode});42 43        while (!pq.isEmpty()) {44            int[] current = pq.poll();45            int d = current[0];46            int u = current[1];47 48            if (d > dist[u]) {49                continue;50            }51 52            for (int[] neighbor : adj.get(u)) {53                int v = neighbor[0];54                int weight = neighbor[1];55                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {56                    dist[v] = dist[u] + weight;57                    pq.offer(new int[]{dist[v], v});58                }59            }60        }61        return dist;62    }63}

Complexity

Time

O(n * (E + n) log n). We run Dijkstra's algorithm `n` times. Each run of Dijkstra's with a binary heap has a complexity of `O((E+n) log n)`. For a dense graph, this approaches `O(n^3 log n)`.

Space

O(n + E), where `n` is the number of cities and `E` is the number of edges. This is for storing the adjacency list. In the worst case, `E` can be `O(n^2)`, making the space complexity `O(n^2)`.

Trade-offs

Pros

Conceptually straightforward, as it directly applies a standard SSSP algorithm.
Can be more efficient than Floyd-Warshall on very sparse graphs where E is much smaller than n^2.

Cons

For dense graphs, where the number of edges E is close to n^2, the time complexity O(n * E log n) becomes O(n^3 log n), which is less efficient than the Floyd-Warshall algorithm's O(n^3).
The implementation is slightly more complex than Floyd-Warshall, involving a priority queue and adjacency list setup for each of the n runs.

The Floyd-Warshall algorithm is a classic dynamic programming approach for the all-pairs shortest path (APSP) problem. Given that we need to know the distances between all pairs of cities to solve this problem, Floyd-Warshall is a very natural and efficient choice, especially for the given constraints where n is up to 100. It calculates the shortest paths between all pairs of nodes in a single, unified process.

Algorithm

Initialize Distance Matrix: Create an n x n matrix dist to store the shortest paths between all pairs of cities. Initialize dist[i][i] = 0 for all i, and dist[i][j] = infinity for all i != j.
Populate Initial Distances: Iterate through the edges array. For each edge [u, v, w], set dist[u][v] = w and dist[v][u] = w.
Apply Floyd-Warshall: Use three nested loops to find all-pairs shortest paths. The loops iterate through intermediate nodes k, source nodes i, and destination nodes j.
- for k from 0 to n-1:
- for i from 0 to n-1:
- for j from 0 to n-1:
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Find the Result City: After the dist matrix is computed, iterate through each city i from 0 to n-1.
- For each i, count the number of other cities j where dist[i][j] <= distanceThreshold.
- Keep track of the city with the minimum count. If the current city's count is less than or equal to the minimum count found so far, update the result to the current city i. This handles the tie-breaking rule.
Return Result: The final city stored is the answer.

Walkthrough

This method begins by setting up an n x n distance matrix. Initially, the distance from a city to itself is 0, the distance between directly connected cities is their edge weight, and all other distances are infinite. The algorithm then systematically improves these path estimates. It iterates through every city k and considers it as a potential intermediate stop in the path from any city i to any city j. It updates the distance dist[i][j] if the path going through k (dist[i][k] + dist[k][j]) is shorter. After iterating through all possible intermediate cities k, the matrix contains the shortest path distances between every pair of cities. With this complete information, we can simply iterate through each city, count its neighbors within the distance threshold, and find the city that minimizes this count, respecting the tie-breaker rule.

1import java.util.Arrays;2 3class Solution {4    public int findTheCity(int n, int[][] edges, int distanceThreshold) {5        int[][] dist = new int[n][n];6        // Use a large number for infinity, but not so large it overflows when added.7        int INF = 100000000;8 9        for (int i = 0; i < n; i++) {10            Arrays.fill(dist[i], INF);11            dist[i][i] = 0;12        }13 14        for (int[] edge : edges) {15            int u = edge[0];16            int v = edge[1];17            int w = edge[2];18            dist[u][v] = w;19            dist[v][u] = w;20        }21 22        for (int k = 0; k < n; k++) {23            for (int i = 0; i < n; i++) {24                for (int j = 0; j < n; j++) {25                    if (dist[i][k] < INF && dist[k][j] < INF) { // Avoid overflow26                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);27                    }28                }29            }30        }31 32        int minReachableCities = n;33        int resultCity = -1;34 35        for (int i = 0; i < n; i++) {36            int reachableCount = 0;37            for (int j = 0; j < n; j++) {38                if (i != j && dist[i][j] <= distanceThreshold) {39                    reachableCount++;40                }41            }42 43            if (reachableCount <= minReachableCities) {44                minReachableCities = reachableCount;45                resultCity = i;46            }47        }48 49        return resultCity;50    }51}

Complexity

Time

O(n^3). The algorithm is dominated by the three nested loops, each running `n` times. The final step to find the result city takes `O(n^2)`, which is subsumed by `O(n^3)`.

Space

O(n^2), for storing the `n x n` distance matrix.

Trade-offs

Pros

Generally more efficient for this problem's constraints (n <= 100) than running Dijkstra from each node, especially for dense graphs.
The implementation is very concise and straightforward due to its systematic, triple-loop structure.
Its O(n^3) performance is predictable and not dependent on the graph's structure (sparse vs. dense).

Cons

Can be slower than repeated Dijkstra's on very sparse graphs, although this is often not a significant factor for the given constraints.
Requires O(n^2) space unconditionally, which might be high if memory is extremely constrained and the graph is sparse.

Solutions

Solution

1class Solution {2private3  int n;4private5  int[][] g;6private7  int[] dist;8private9  boolean[] vis;10private11  final int inf = 1 << 30;12private13  int distanceThreshold;14public15  int findTheCity(int n, int[][] edges, int distanceThreshold) {16    this.n = n;17    this.distanceThreshold = distanceThreshold;18    g = new int[n][n];19    dist = new int[n];20    vis = new boolean[n];21    for (var e : g) {22      Arrays.fill(e, inf);23    }24    for (var e : edges) {25      int f = e[0], t = e[1], w = e[2];26      g[f][t] = w;27      g[t][f] = w;28    }29    int ans = n, cnt = inf;30    for (int i = n - 1; i >= 0; --i) {31      int t = dijkstra(i);32      if (t < cnt) {33        cnt = t;34        ans = i;35      }36    }37    return ans;38  }39private40  int dijkstra(int u) {41    Arrays.fill(dist, inf);42    Arrays.fill(vis, false);43    dist[u] = 0;44    for (int i = 0; i < n; ++i) {45      int k = -1;46      for (int j = 0; j < n; ++j) {47        if (!vis[j] && (k == -1 || dist[k] > dist[j])) {48          k = j;49        }50      }51      vis[k] = true;52      for (int j = 0; j < n; ++j) {53        dist[j] = Math.min(dist[j], dist[k] + g[k][j]);54      }55    }56    int cnt = 0;57    for (int d : dist) {58      if (d <= distanceThreshold) {59        ++cnt;60      }61    }62    return cnt;63  }64}

1function findTheCity ( n , edges , distanceThreshold ) { const g = Array . from ({ length : n }, () => Array ( n ). fill ( Infinity )); const dist = Array ( n ). fill ( Infinity ); const vis = Array ( n ). fill ( false ); for ( const [ f , t , w ] of edges ) { g [ f ][ t ] = g [ t ][ f ] = w ; } const dijkstra = u => { dist . fill ( Infinity ); vis . fill ( false ); dist [ u ] = 0 ; for ( let i = 0 ; i < n ; ++ i ) { let k = - 1 ; for ( let j = 0 ; j < n ; ++ j ) { if ( ! vis [ j ] && ( k === - 1 || dist [ j ] < dist [ k ])) { k = j ; } } vis [ k ] = true ; for ( let j = 0 ; j < n ; ++ j ) { dist [ j ] = Math . min ( dist [ j ], dist [ k ] + g [ k ][ j ]); } } return dist . filter ( d => d <= distanceThreshold ). length ; }; let ans = n ; let cnt = Infinity ; for ( let i = n - 1 ; i >= 0 ; -- i ) { const t = dijkstra ( i ); if ( t < cnt ) { cnt = t ; ans = i ; } } return ans ; }

1class Solution {2public:3  int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold) {4    int g[n][n];5    int dist[n];6    bool vis[n];7    memset(g, 0x3f, sizeof(g));8    for (auto &e : edges) {9      int f = e[0], t = e[1], w = e[2];10      g[f][t] = g[t][f] = w;11    }12    auto dijkstra = [&](int u) {13      memset(dist, 0x3f, sizeof(dist));14      memset(vis, 0, sizeof(vis));15      dist[u] = 0;16      for (int i = 0; i < n; ++i) {17        int k = -1;18        for (int j = 0; j < n; ++j) {19          if (!vis[j] && (k == -1 || dist[j] < dist[k])) {20            k = j;21          }22        }23        vis[k] = true;24        for (int j = 0; j < n; ++j) {25          dist[j] = min(dist[j], dist[k] + g[k][j]);26        }27      }28      return count_if(dist, dist + n,29                      [&](int d) { return d <= distanceThreshold; });30    };31    int ans = n, cnt = n + 1;32    for (int i = n - 1; ~i; --i) {33      int t = dijkstra(i);34      if (t < cnt) {35        cnt = t;36        ans = i;37      }38    }39    return ans;40  }41};

1class Solution:2    # dist[j] = min(dist[j], dist[k] + g[k][j]) if dist [ k ] + g [ k ][ j ] < dist [ j ]: dist [ j ] = dist [ k ] + g [ k ][ j ] return sum ( d <= distanceThreshold for d in dist ) g = [[ inf ] * n for _ in range ( n )] for f , t , w in edges : g [ f ][ t ] = g [ t ][ f ] = w ans , cnt = n , inf for i in range ( n - 1 , - 1 , - 1 ): if ( t : = dijkstra ( i )) < cnt : cnt , ans = t , i return ans3    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int: def dijkstra(u: int) -> int: dist = [inf] * n dist[u] = 0 vis = [False] * n 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 for j in range(n):

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem