# Find the City With the Smallest Number of Neighbors at a Threshold Distance
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance)
Canonical: https://scaleengineer.com/dsa/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Graph
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia)
---
## Problem
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:**

![](https://assets.glich.co/dsa/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/image0.png)

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

![](https://assets.glich.co/dsa/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/image1.png)

**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
## Approach 1: Dijkstra's Algorithm from Each City
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.
**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)`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Approach 2: Floyd-Warshall Algorithm
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dist = new int[n][n];
        // Use a large number for infinity, but not so large it overflows when added.
        int INF = 100000000;

        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            dist[u][v] = w;
            dist[v][u] = w;
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] < INF && dist[k][j] < INF) { // Avoid overflow
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        int minReachableCities = n;
        int resultCity = -1;

        for (int i = 0; i < n; i++) {
            int reachableCount = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i][j] <= distanceThreshold) {
                    reachableCount++;
                }
            }

            if (reachableCount <= minReachableCities) {
                minReachableCities = reachableCount;
                resultCity = i;
            }
        }

        return resultCity;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
function 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 ; }
```

### CPP

```cpp
class Solution {
public:
  int findTheCity(int n, vector<vector<int>> &edges, int distanceThreshold) {
    int g[n][n];
    int dist[n];
    bool vis[n];
    memset(g, 0x3f, sizeof(g));
    for (auto &e : edges) {
      int f = e[0], t = e[1], w = e[2];
      g[f][t] = g[t][f] = w;
    }
    auto dijkstra = [&](int u) {
      memset(dist, 0x3f, sizeof(dist));
      memset(vis, 0, sizeof(vis));
      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[j] < dist[k])) {
            k = j;
          }
        }
        vis[k] = true;
        for (int j = 0; j < n; ++j) {
          dist[j] = min(dist[j], dist[k] + g[k][j]);
        }
      }
      return count_if(dist, dist + n,
                      [&](int d) { return d <= distanceThreshold; });
    };
    int ans = n, cnt = n + 1;
    for (int i = n - 1; ~i; --i) {
      int t = dijkstra(i);
      if (t < cnt) {
        cnt = t;
        ans = i;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    # 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 ans
    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):

```