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

medium floyd-warshall graph

Problem

Given n cities and weighted undirected edges, find the city with the smallest number of other cities reachable within distance ≤ distanceThreshold. If multiple cities tie, return the one with the greatest index.

Inputn = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], threshold = 4

Output3

Reachable counts: city 0 → 3, city 1 → 3, city 2 → 3, city 3 → 3. Tie ⇒ return 3.

edges (JSON)

threshold

def find_the_city(n, edges, threshold):
    INF = float('inf')
    d = [[INF] * n for _ in range(n)]
    for i in range(n): d[i][i] = 0
    for a, b, w in edges:
        d[a][b] = d[b][a] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    best_city, best_cnt = -1, n + 1
    for i in range(n):
        cnt = sum(1 for j in range(n) if j != i and d[i][j] <= threshold)
        if cnt <= best_cnt:
            best_cnt = cnt; best_city = i
    return best_city

function findTheCity(n, edges, threshold) {
  const INF = 1e15;
  const d = Array.from({ length: n }, () => new Array(n).fill(INF));
  for (let i = 0; i < n; i++) d[i][i] = 0;
  for (const [a, b, w] of edges) { d[a][b] = w; d[b][a] = w; }
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
  let best = -1, cnt = n + 1;
  for (let i = 0; i < n; i++) {
    let c = 0;
    for (let j = 0; j < n; j++) if (i !== j && d[i][j] <= threshold) c++;
    if (c <= cnt) { cnt = c; best = i; }
  }
  return best;
}

class Solution {
    public int findTheCity(int n, int[][] edges, int threshold) {
        int INF = (int)1e9;
        int[][] d = new int[n][n];
        for (int[] r : d) Arrays.fill(r, INF);
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (int[] e : edges) { d[e[0]][e[1]] = e[2]; d[e[1]][e[0]] = e[2]; }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        int best = -1, cnt = n + 1;
        for (int i = 0; i < n; i++) {
            int c = 0;
            for (int j = 0; j < n; j++) if (i != j && d[i][j] <= threshold) c++;
            if (c <= cnt) { cnt = c; best = i; }
        }
        return best;
    }
}

int findTheCity(int n, vector<vector<int>>& edges, int threshold) {
    int INF = 1e9;
    vector<vector<int>> d(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (auto& e : edges) { d[e[0]][e[1]] = e[2]; d[e[1]][e[0]] = e[2]; }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
    int best = -1, cnt = n + 1;
    for (int i = 0; i < n; i++) {
        int c = 0;
        for (int j = 0; j < n; j++) if (i != j && d[i][j] <= threshold) c++;
        if (c <= cnt) { cnt = c; best = i; }
    }
    return best;
}

Explanation

We need the shortest distance between every pair of cities, then for each city count how many others sit within the threshold. The cleanest way to get all those pairwise distances at once is the Floyd-Warshall algorithm.

We build a matrix d where d[i][j] is the shortest known distance from city i to city j. Start with 0 on the diagonal, the direct edge weights where they exist, and INF everywhere else.

Floyd-Warshall then tries every city k as a possible middle stop: if going i → k → j is shorter than the current d[i][j], we update it. After looping k over all cities, d holds true shortest paths between all pairs.

Now for each city i we count the cities j with d[i][j] <= threshold. We track the smallest count, and because we use <= while scanning cities in increasing order, a tie naturally keeps the largest index.

Example: n = 4, threshold 4. Every city ends up able to reach 3 others within distance 4, so all counts tie at 3, and the rule picks the biggest index, city 3.

Time: O(n³) Space: O(n²)