Problem 26.5 · Shortest PathsMedium

Find the City With the Smallest Number of Neighbors

What it teaches: All-pairs distances with Floyd-Warshall on a small graph.

Practise it on judges as “Find the City With the Smallest Number of Neighbors at a Threshold Distance”.

The problem

Given n cities and weighted undirected edges, return the city with the fewest other cities reachable within distanceThreshold. On a tie, return the city with the largest number.

Example 1

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

Constraints

2 ≤ n ≤ 100

Pattern clues in the wording

→ Distances between every pair
→ Small n

These clues point to Dijkstra's Shortest Path: Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 4 edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] distanceThreshold = 4	3
2	n = 5 edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]] distanceThreshold = 2	0

From slow to fast

Approaches

1. Floyd-Warshall · O(n³)

Floyd-Warshall

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

All-pairs distances; for each city count others within the threshold; pick the smallest count, preferring the larger index on ties.

Approach 1

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = 1_000_000_000;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = i == j ? 0 : INF;
        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 answer = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) if (i != j && d[i][j] <= distanceThreshold) count++;
            if (count <= fewest) { fewest = count; answer = i; }
        }
        return answer;
    }
}

Verdict: Simplest correct choice for small n.

Before you submit

Edge cases and common mistakes

Test these inputs

Every city isolated (largest index)
Ties

Mistakes people make

Using < instead of <= for the tie-break (returns the smallest index).

Interview

Follow-up questions

What if n were 10⁴ with few edges?

Command Palette

The problem

Approaches

Floyd-Warshall

Edge cases and common mistakes

Follow-up questions