Scale Engineer

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
Dynamic Programming
Algorithms
Shortest Path
Data structures
Graph
Companies
Expedia

Prompt

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, 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 <= fromi < toi < n
  • 1 <= weighti, distanceThreshold <= 10^4
  • All pairs (fromi, toi) 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.

import java.util.*; class Solution {    public int findTheCity(int n, int[][] edges, int distanceThreshold) {        List<List<int[]>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] edge : edges) {            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});        }         int minReachableCities = n;        int resultCity = -1;         for (int i = 0; i < n; i++) {            int[] dist = dijkstra(n, adj, i);            int reachableCount = 0;            for (int j = 0; j < n; j++) {                if (i != j && dist[j] <= distanceThreshold) {                    reachableCount++;                }            }             if (reachableCount <= minReachableCities) {                minReachableCities = reachableCount;                resultCity = i;            }        }        return resultCity;    }     private int[] dijkstra(int n, List<List<int[]>> adj, int startNode) {        int[] dist = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[startNode] = 0;         // PriorityQueue stores {distance, node}        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));        pq.offer(new int[]{0, startNode});         while (!pq.isEmpty()) {            int[] current = pq.poll();            int d = current[0];            int u = current[1];             if (d > dist[u]) {                continue;            }             for (int[] neighbor : adj.get(u)) {                int v = neighbor[0];                int weight = neighbor[1];                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {                    dist[v] = dist[u] + weight;                    pq.offer(new int[]{dist[v], v});                }            }        }        return dist;    }}

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.

Solutions

class Solution {private  int n;private  int[][] g;private  int[] dist;private  boolean[] vis;private  final int inf = 1 << 30;private  int distanceThreshold;public  int findTheCity(int n, int[][] edges, int distanceThreshold) {    this.n = n;    this.distanceThreshold = distanceThreshold;    g = new int[n][n];    dist = new int[n];    vis = new boolean[n];    for (var e : g) {      Arrays.fill(e, inf);    }    for (var e : edges) {      int f = e[0], t = e[1], w = e[2];      g[f][t] = w;      g[t][f] = w;    }    int ans = n, cnt = inf;    for (int i = n - 1; i >= 0; --i) {      int t = dijkstra(i);      if (t < cnt) {        cnt = t;        ans = i;      }    }    return ans;  }private  int dijkstra(int u) {    Arrays.fill(dist, inf);    Arrays.fill(vis, false);    dist[u] = 0;    for (int i = 0; i < n; ++i) {      int k = -1;      for (int j = 0; j < n; ++j) {        if (!vis[j] && (k == -1 || dist[k] > dist[j])) {          k = j;        }      }      vis[k] = true;      for (int j = 0; j < n; ++j) {        dist[j] = Math.min(dist[j], dist[k] + g[k][j]);      }    }    int cnt = 0;    for (int d : dist) {      if (d <= distanceThreshold) {        ++cnt;      }    }    return cnt;  }}

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 →

Next problem