Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

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

MEDIUMProblemSolveExternal Links

Description

You are given n cities labeled from 0 to n - 1 and a list of bidirectional weighted edges. Each edge is described as [from, to, weight], indicating a road between two cities with a certain travel cost.

Given an integer distanceThreshold, your task is to determine which city can reach the fewest other cities when only paths with total distance at most distanceThreshold are considered.

If multiple cities share the same minimum count of reachable neighbors, return the city with the greatest index (the highest-numbered city).

Examples

Example 1

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4

Output: 3

Explanation:

We need to count how many other cities each city can reach within distance 4:

  • City 0 can reach City 1 (distance 3) and City 2 (distance 4) → 2 neighbors
  • City 1 can reach City 0 (distance 3), City 2 (distance 1), and City 3 (distance 2) → 3 neighbors
  • City 2 can reach City 0 (distance 4), City 1 (distance 1), and City 3 (distance 1) → 3 neighbors
  • City 3 can reach City 1 (distance 2) and City 2 (distance 1) → 2 neighbors

Cities 0 and 3 are tied with 2 neighbors each. Since City 3 has the greater index, we return 3.

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:

Counting reachable cities within distance 2:

  • City 0 can reach City 1 (distance 2) → 1 neighbor
  • City 1 can reach City 0 (distance 2) and City 4 (distance 2) → 2 neighbors
  • City 2 can reach City 3 (distance 1) and City 4 (distance 2) → 2 neighbors
  • City 3 can reach City 2 (distance 1) and City 4 (distance 1) → 2 neighbors
  • City 4 can reach City 1 (distance 2), City 3 (distance 1), and City 2 (distance 2) → 3 neighbors

City 0 has the fewest reachable neighbors (just 1), so we return 0.

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.

Editorial

Brute Force - Dijkstra from Every City

Intuition

The problem boils down to one fundamental question: for each city, how many other cities can it reach within the given distance budget?

To answer that, we need to know the shortest path from every city to every other city. Why shortest paths? Because if even the shortest route between two cities exceeds the threshold, then no valid route exists. And if the shortest route is within the threshold, that city counts as reachable.

The most straightforward strategy is to run a single-source shortest path algorithm from each city individually. For weighted graphs with non-negative edge weights, Dijkstra's algorithm is the classic choice.

Here we use a simple version of Dijkstra that operates on an adjacency matrix. For each source city, we compute shortest distances to all other cities, then count how many of those distances fall within the threshold. After processing all cities, we pick the one with the smallest count (breaking ties by choosing the higher-numbered city).

Think of it like planning trips from every town on a map: you calculate the cheapest fare to every other town, then count how many destinations are affordable. The town with the fewest affordable destinations wins.

Step-by-Step Explanation

Let's trace through Example 1: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4.

Step 1: Build the adjacency matrix.

     0    1    2    3
0 [ inf,  3,  inf, inf ]
1 [  3,  inf,  1,   4  ]
2 [ inf,  1,  inf,  1  ]
3 [ inf,  4,   1,  inf ]

Step 2: Run Dijkstra from City 3.

  • Initial distances: [inf, inf, inf, 0]. Pick City 3 (dist=0).
  • Relax from City 3: dist[1] = min(inf, 0+4) = 4, dist[2] = min(inf, 0+1) = 1.
  • Distances now: [inf, 4, 1, 0]. Pick City 2 (dist=1).
  • Relax from City 2: dist[1] = min(4, 1+1) = 2, dist[0] = min(inf, 1+inf) = inf.
  • Distances now: [inf, 2, 1, 0]. Pick City 1 (dist=2).
  • Relax from City 1: dist[0] = min(inf, 2+3) = 5.
  • Final distances from City 3: [5, 2, 1, 0].
  • Cities within threshold 4 (excluding self): City 1 (dist 2) ✓, City 2 (dist 1) ✓, City 0 (dist 5) ✗.
  • Count = 2.

Step 3: Run Dijkstra from City 2.

  • Final distances from City 2: [4, 1, 0, 1].
  • Within threshold 4: City 0 (4) ✓, City 1 (1) ✓, City 3 (1) ✓.
  • Count = 3.

Step 4: Run Dijkstra from City 1.

  • Final distances from City 1: [3, 0, 1, 2].
  • Within threshold 4: City 0 (3) ✓, City 2 (1) ✓, City 3 (2) ✓.
  • Count = 3.

Step 5: Run Dijkstra from City 0.

  • Final distances from City 0: [0, 3, 4, 5].
  • Within threshold 4: City 1 (3) ✓, City 2 (4) ✓, City 3 (5) ✗.
  • Count = 2.

Step 6: Compare counts (processing in reverse order for tie-breaking):

  • City 3: count=2 → best so far (ans=3, minCount=2)
  • City 2: count=3 → 3 ≥ 2, skip
  • City 1: count=3 → 3 ≥ 2, skip
  • City 0: count=2 → 2 is NOT < 2, skip (tie, keep City 3)

Result: Return 3.

Dijkstra from City 3 — Finding Shortest Paths — Watch Dijkstra's algorithm explore outward from City 3, computing shortest distances to every other city and determining which are reachable within the threshold.

Algorithm

  1. Build an n × n adjacency matrix initialized with infinity. For each edge [u, v, w], set matrix[u][v] = matrix[v][u] = w.
  2. For each city i from n-1 down to 0:
    a. Run Dijkstra's algorithm from city i to find shortest distances to all other cities.
    b. Count how many other cities have shortest distance ≤ distanceThreshold.
  3. Track the city with the smallest count. If a new city has a strictly smaller count, update the answer.
  4. Return the answer city. (Reverse iteration ensures the highest-numbered city wins on ties.)

Code

#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        // Build adjacency matrix
        vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2));
        for (auto& e : edges) {
            g[e[0]][e[1]] = e[2];
            g[e[1]][e[0]] = e[2];
        }
        
        int ans = -1, minCount = n + 1;
        
        // Try each city as source (reverse order for tie-breaking)
        for (int i = n - 1; i >= 0; i--) {
            int count = dijkstra(i, n, g, distanceThreshold);
            if (count < minCount) {
                minCount = count;
                ans = i;
            }
        }
        return ans;
    }
    
private:
    int dijkstra(int src, int n, vector<vector<int>>& g, int threshold) {
        vector<int> dist(n, INT_MAX / 2);
        vector<bool> vis(n, false);
        dist[src] = 0;
        
        for (int iter = 0; iter < n; iter++) {
            // Find unvisited city with minimum distance
            int k = -1;
            for (int j = 0; j < n; j++) {
                if (!vis[j] && (k == -1 || dist[j] < dist[k]))
                    k = j;
            }
            vis[k] = true;
            
            // Relax edges from city k
            for (int j = 0; j < n; j++) {
                if (dist[k] + g[k][j] < dist[j])
                    dist[j] = dist[k] + g[k][j];
            }
        }
        
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (j != src && dist[j] <= threshold)
                count++;
        }
        return count;
    }
};
class Solution:
    def findTheCity(self, n: int, edges: list[list[int]], distanceThreshold: int) -> int:
        # Build adjacency matrix
        INF = float('inf')
        g = [[INF] * n for _ in range(n)]
        for u, v, w in edges:
            g[u][v] = w
            g[v][u] = w
        
        def dijkstra(src: int) -> int:
            dist = [INF] * n
            dist[src] = 0
            vis = [False] * n
            
            for _ in range(n):
                # Pick unvisited city with smallest distance
                k = -1
                for j in range(n):
                    if not vis[j] and (k == -1 or dist[j] < dist[k]):
                        k = j
                vis[k] = True
                
                # Relax neighbors
                for j in range(n):
                    if dist[k] + g[k][j] < dist[j]:
                        dist[j] = dist[k] + g[k][j]
            
            return sum(1 for j in range(n) if j != src and dist[j] <= distanceThreshold)
        
        ans, min_count = -1, n + 1
        for i in range(n - 1, -1, -1):
            count = dijkstra(i)
            if count < min_count:
                min_count = count
                ans = i
        return ans
import java.util.Arrays;

class Solution {
    private int[][] g;
    private int n;
    
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        this.n = n;
        // Build adjacency matrix
        g = new int[n][n];
        int INF = Integer.MAX_VALUE / 2;
        for (int[] row : g) Arrays.fill(row, INF);
        for (int[] e : edges) {
            g[e[0]][e[1]] = e[2];
            g[e[1]][e[0]] = e[2];
        }
        
        int ans = -1, minCount = n + 1;
        for (int i = n - 1; i >= 0; i--) {
            int count = dijkstra(i, distanceThreshold);
            if (count < minCount) {
                minCount = count;
                ans = i;
            }
        }
        return ans;
    }
    
    private int dijkstra(int src, int threshold) {
        int INF = Integer.MAX_VALUE / 2;
        int[] dist = new int[n];
        boolean[] vis = new boolean[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        
        for (int iter = 0; iter < n; iter++) {
            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++) {
                if (dist[k] + g[k][j] < dist[j])
                    dist[j] = dist[k] + g[k][j];
            }
        }
        
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (j != src && dist[j] <= threshold)
                count++;
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n³)

We run Dijkstra's algorithm n times (once per city). Each Dijkstra run uses the simple O(n²) implementation: n iterations to select the minimum-distance unvisited node (each taking O(n) to scan), plus O(n) relaxation per iteration. So each run is O(n²), and n runs yield O(n³) total.

Space Complexity: O(n²)

The adjacency matrix occupies O(n²) space. Each Dijkstra invocation uses O(n) for the distance and visited arrays, but these are reused across calls. The dominant cost is the adjacency matrix.

Why This Approach Is Not Efficient

While O(n³) does pass for n ≤ 100, running a full Dijkstra from every single city involves a lot of redundant computation. Each Dijkstra run independently discovers shortest paths without leveraging anything learned from previous runs.

The fundamental inefficiency is that we solve n separate single-source shortest path problems, when the real need is all-pairs shortest paths. Algorithms like Floyd-Warshall compute all-pairs shortest paths in a single unified pass, which — while having the same O(n³) time complexity — is often faster in practice due to better cache behavior and a simpler inner loop (three nested for-loops with no priority queue overhead).

Moreover, if we ever needed to handle this on denser graphs or with slightly larger n, the repeated Dijkstra approach would become harder to optimize compared to the elegant matrix-based Floyd-Warshall method.

Optimal Approach - Floyd-Warshall

Intuition

Instead of running Dijkstra n times, we can compute all-pairs shortest paths in one shot using the Floyd-Warshall algorithm.

The key idea behind Floyd-Warshall is beautifully simple: consider every city as a potential intermediate stop. For each pair of cities (i, j), ask: "Is it cheaper to go from i to j through city k than the best route we've found so far?" By systematically trying every city k as an intermediate, we guarantee finding the shortest path between every pair.

Imagine you're a travel agent. Initially, you only know the direct flight prices between cities. Then a new hub airport (city k) opens — you check if routing through that hub gives a cheaper fare for any pair of cities. You repeat this for every possible hub. After considering all hubs, you have the cheapest fare for every origin-destination pair.

Once we have the complete shortest-distance matrix, the counting step is trivial: for each city, scan its row and count entries ≤ distanceThreshold. The city with the fewest such entries (highest index on tie) is our answer.

Diagram showing Floyd-Warshall's intermediate city concept: checking if path i→k→j is shorter than direct path i→j
Diagram showing Floyd-Warshall's intermediate city concept: checking if path i→k→j is shorter than direct path i→j

Step-by-Step Explanation

Let's trace Floyd-Warshall on Example 1: n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold=4.

Step 1: Initialize the distance matrix with direct edge weights.

     0    1    2    3
0 [  0,   3,  inf, inf ]
1 [  3,   0,   1,   4  ]
2 [ inf,  1,   0,   1  ]
3 [ inf,  4,   1,   0  ]

Step 2: Consider k=0 as intermediate. For every pair (i,j), check if going through 0 is better.

  • dist[1][2]: min(1, dist[1][0]+dist[0][2]) = min(1, 3+inf) = 1. No change.
  • dist[1][3]: min(4, 3+inf) = 4. No change.
  • No path through city 0 improves anything because city 0 only connects to city 1.

Step 3: Consider k=1 as intermediate.

  • dist[0][2]: min(inf, dist[0][1]+dist[1][2]) = min(inf, 3+1) = 4. Updated!
  • dist[0][3]: min(inf, dist[0][1]+dist[1][3]) = min(inf, 3+4) = 7. Updated!
  • dist[2][0]: min(inf, 1+3) = 4. Updated! (symmetric)
  • dist[2][3]: min(1, 1+4) = 1. No change.
  • dist[3][0]: min(inf, 4+3) = 7. Updated!
  • dist[3][2]: min(1, 4+1) = 1. No change.

Step 4: Consider k=2 as intermediate.

  • dist[0][3]: min(7, dist[0][2]+dist[2][3]) = min(7, 4+1) = 5. Updated!
  • dist[1][3]: min(4, dist[1][2]+dist[2][3]) = min(4, 1+1) = 2. Updated!
  • dist[3][0]: min(7, 1+4) = 5. Updated!
  • dist[3][1]: min(4, 1+1) = 2. Updated!

Step 5: Consider k=3 as intermediate.

  • dist[0][1]: min(3, dist[0][3]+dist[3][1]) = min(3, 5+2) = 3. No change.
  • dist[0][2]: min(4, 5+1) = 4. No change.
  • dist[1][0]: min(3, 2+5) = 3. No change.
  • No improvements. The matrix is now final.

Step 6: Final shortest-distance matrix:

     0   1   2   3
0 [  0,  3,  4,  5 ]
1 [  3,  0,  1,  2 ]
2 [  4,  1,  0,  1 ]
3 [  5,  2,  1,  0 ]

Step 7: Count neighbors within threshold 4:

  • City 0: distances [3, 4, 5] → 3≤4 ✓, 4≤4 ✓, 5>4 ✗ → 2 neighbors
  • City 1: distances [3, 1, 2] → all ≤ 4 → 3 neighbors
  • City 2: distances [4, 1, 1] → all ≤ 4 → 3 neighbors
  • City 3: distances [5, 2, 1] → 5>4 ✗, 2≤4 ✓, 1≤4 ✓ → 2 neighbors

Step 8: Cities 0 and 3 both have 2 neighbors. Pick City 3 (higher index).

Result: Return 3.

Floyd-Warshall — Building All-Pairs Shortest Paths — Watch the distance matrix evolve as we try each city as an intermediate stop. Each update means we discovered a shorter path that routes through the current intermediate city.

Algorithm

  1. Initialize an n × n distance matrix dist with infinity. Set dist[i][i] = 0 for all cities. For each edge [u, v, w], set dist[u][v] = dist[v][u] = w.
  2. Run Floyd-Warshall: for each intermediate city k from 0 to n-1, for each pair (i, j), update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  3. For each city i, count how many other cities j satisfy dist[i][j] ≤ distanceThreshold.
  4. Return the city with the smallest count. On ties, return the city with the highest index.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        const int INF = 1e9;
        // Initialize distance matrix
        vector<vector<int>> dist(n, vector<int>(n, INF));
        for (int i = 0; i < n; i++) dist[i][i] = 0;
        for (auto& e : edges) {
            dist[e[0]][e[1]] = e[2];
            dist[e[1]][e[0]] = e[2];
        }
        
        // Floyd-Warshall: try every city as intermediate
        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] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        // Find city with minimum reachable neighbors
        int ans = -1, minCount = n + 1;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i][j] <= distanceThreshold)
                    count++;
            }
            if (count <= minCount) {
                minCount = count;
                ans = i;
            }
        }
        return ans;
    }
};
class Solution:
    def findTheCity(self, n: int, edges: list[list[int]], distanceThreshold: int) -> int:
        INF = float('inf')
        
        # Initialize distance matrix
        dist = [[INF] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w
        
        # Floyd-Warshall: try every city as intermediate
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        # Find city with minimum reachable neighbors
        ans, min_count = -1, n + 1
        for i in range(n):
            count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
            if count <= min_count:
                min_count = count
                ans = i
        
        return ans
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = (int) 1e9;
        
        // Initialize distance matrix
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            java.util.Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }
        for (int[] e : edges) {
            dist[e[0]][e[1]] = e[2];
            dist[e[1]][e[0]] = e[2];
        }
        
        // Floyd-Warshall: try every city as intermediate
        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] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        // Find city with minimum reachable neighbors
        int ans = -1, minCount = n + 1;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i][j] <= distanceThreshold)
                    count++;
            }
            if (count <= minCount) {
                minCount = count;
                ans = i;
            }
        }
        return ans;
    }
}

Complexity Analysis

Time Complexity: O(n³)

The Floyd-Warshall algorithm has three nested loops, each running from 0 to n-1, giving O(n³). The subsequent counting phase is O(n²), which is dominated by the Floyd-Warshall step. Although this is the same asymptotic complexity as the Dijkstra approach, Floyd-Warshall is typically faster in practice for dense graphs because its inner loop is a simple comparison and addition — no priority queue management, no visited-set bookkeeping.

Space Complexity: O(n²)

The n × n distance matrix is the dominant space cost. Unlike the Dijkstra approach, Floyd-Warshall modifies this matrix in-place, so no additional per-source arrays are needed during computation.