Get started

Find the City With the Smallest Number of Neighbors at a Threshold Distance — Medium Problem & Solution

There are n cities numbered 0 to n - 1. Each edges[i] = [from, to, weight] is a two-way road of length weight between cities from and to.

Problem statement

There are n cities numbered 0 to n - 1. Each edges[i] = [from, to, weight] is a two-way road of length weight between cities from and to.

For a city c, count the other cities whose shortest road distance from c is at most distanceThreshold.

Return the city with the smallest such count. If several cities tie, return the one with the largest number.

Example 1

Input: n = 4, edges = [[0,1,2],[1,2,2],[2,3,5],[0,3,9]], distanceThreshold = 5
Output: 3
Explanation: Within distance 5: city 0 reaches {1, 2}, city 1 reaches {0, 2}, city 2 reaches {0, 1, 3}, city 3 reaches only {2}.

Example 2

Input: n = 3, edges = [[0,1,1],[1,2,1]], distanceThreshold = 1
Output: 2
Explanation: Cities 0 and 2 both reach one neighbour; the larger number wins the tie.

Constraints

  • 2 <= n <= 100
  • 1 <= edges.length <= n * (n - 1) / 2
  • edges[i].length == 3
  • 0 <= from < to < n
  • 1 <= weight, distanceThreshold <= 10^4
  • all pairs (from, to) are distinct

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

Compute all-pairs shortest paths, then pick the city with the fewest others within reach, breaking ties toward the larger index.

Approach

  1. Fill an n × n distance table with 0 on the diagonal, the road weight for each road, and a large sentinel elsewhere.
  2. Floyd–Warshall: for every intermediate k, and every pair (i, j), relax d[i][j] with d[i][k] + d[k][j].
  3. For each city count the others with d[c][j] <= distanceThreshold.
  4. Scan cities from 0 upward, replacing the answer whenever the count is less than or equal to the best so far.

Why it works

After processing intermediates 0..k, d[i][j] holds the shortest path that only passes through those cities, so after all n rounds it is the true shortest distance. Scanning in increasing order with <= makes the last city achieving the minimum — the largest index — the answer.

Complexity

  • Time — O(n³)
  • Space — O(n²)

Pitfalls

  • Pick a sentinel whose double still fits in a 32-bit int (for example 10^8), or guard the addition.
  • Roads are two-way: set both d[u][v] and d[v][u].
  • Ties go to the larger city number — using < instead of <= returns the smallest.

Reference solution

Python

from typing import List

def findTheCity(n: int, edges: List[List[int]], distanceThreshold: int) -> int:
    INF = 10 ** 8
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        if w < d[u][v]:
            d[u][v] = w
            d[v][u] = w
    for k in range(n):
        dk = d[k]
        for i in range(n):
            di = d[i]
            dik = di[k]
            if dik == INF:
                continue
            for j in range(n):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    best, best_count = -1, n + 1
    for c in range(n):
        cnt = sum(1 for j in range(n) if j != c and d[c][j] <= distanceThreshold)
        if cnt <= best_count:
            best_count = cnt
            best = c
    return best

JavaScript

var findTheCity = function(n, edges, distanceThreshold) {
    var INF = 100000000;
    var d = [];
    for (var i = 0; i < n; i++) {
        d.push([]);
        for (var j = 0; j < n; j++) d[i].push(i === j ? 0 : INF);
    }
    for (var e = 0; e < edges.length; e++) {
        var u = edges[e][0], v = edges[e][1], w = edges[e][2];
        if (w < d[u][v]) { d[u][v] = w; d[v][u] = w; }
    }
    for (var k = 0; k < n; k++)
        for (var a = 0; a < n; a++)
            for (var b = 0; b < n; b++)
                if (d[a][k] + d[k][b] < d[a][b]) d[a][b] = d[a][k] + d[k][b];
    var best = -1, bestCount = n + 1;
    for (var c = 0; c < n; c++) {
        var cnt = 0;
        for (var t = 0; t < n; t++) if (t !== c && d[c][t] <= distanceThreshold) cnt++;
        if (cnt <= bestCount) { bestCount = cnt; best = c; }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 304 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Graph Data Structure