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

Problem in Plain English

Find the city with the fewest other cities reachable within a distance threshold in an undirected weighted graph. Break ties by choosing the largest city number.

Problem Statement

There are n cities numbered from 0 to n - 1. Each entry [u, v, weight] in edges is a bidirectional road. A path’s distance is the sum of its road weights.

Return the city with the smallest count of other cities reachable by a path of total distance at most distanceThreshold. If several cities share the minimum count, return the largest index. A city does not count itself; unreachable cities never count.

Constraints

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2; each edge has three integers.
0 <= u < v < n; all endpoint pairs are distinct.
1 <= weight, distanceThreshold <= 10^4

Examples

Example 1

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

The reachable sets excluding self are {1,2}, {0,2,3}, {0,1,3}, {1,2}. Cities 0 and 3 each have two neighbors; the larger index 3 wins.

Example 2

Input: n = 2, edges = [[0,1,7]], distanceThreshold = 6
Output: 1

The only road exceeds the threshold. Both cities count zero neighbors, so the tie chooses 1.

Example 3

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

Cities 0, 1 and 2 each reach the other two within distance 2. Isolated city 3 reaches nobody, so it uniquely minimizes the count.

Intuition

A road may be expensive even when a cheaper indirect route exists. In Example 1, the road from 1 to 3 costs 4, but traveling through 2 costs 2. Floyd-Warshall stores distances for every pair and allows one more intermediate city in each phase. Once all intermediates are allowed, count each row’s distances within 4: the counts are [2,3,3,2], so the larger tied index 3 wins.

Approaches

Floyd-Warshall

Optimal

Solution Details

Reveal Floyd-Warshall: intuition, complexity, and code

Intuition

Allow intermediate cities one at a time to compute all pairwise distances. With at most 100 cities, the compact cubic matrix algorithm is a practical choice; repeated Dijkstra can be faster on large sparse graphs, but is not needed for these bounds.

Step-by-Step Logic

Initialize the diagonal to 0, road entries symmetrically to their weights, and all other distances to infinity.
Use k as the outer loop. At k = 0 no route in Example 1 improves; at k = 1 discover distances 0 to 2 = 4 and 0 to 3 = 7.
At k = 2 replace distance 1 to 3 = 4 by 1 + 1 = 2, and distance 0 to 3 = 7 by 4 + 1 = 5. Keep symmetry through the full i,j loops.
After k = 3, the matrix rows are [0,3,4,5], [3,0,1,2], [4,1,0,1], [5,2,1,0].
Count entries at most 4 excluding the diagonal. Scan city indices upward and replace the winner on an equal count: [2,3,3,2] selects 3.

Why It Works

Before phase k, dist[i][j] is the shortest path whose internal vertices come from 0 through k - 1. A shortest path allowed to use k either avoids it, keeping the old entry, or splits at k into an i-to-k path and a k-to-j path. Taking the smaller distance covers both possibilities. Positive weights allow shortest paths without cycles, and the zero diagonal keeps in-place updates valid. Induction over k yields all shortest distances; infinity remains for disconnected pairs. Counting exactly the finite distances within the inclusive threshold gives the requested neighbor counts. Updating on ties during ascending index order retains the largest minimizing index.

Dry Run

Floyd-Warshall: variable states at each step
Phase	Changed distances	Selection state
Initialize	d01=3, d12=1, d13=4, d23=1	best count = 4
k=0	none	not counted yet
k=1	d02=4, d03=7 and symmetric entries	not counted yet
k=2	d13=2, d03=5 and symmetric entries	not counted yet
k=3	none	final matrix ready
city 0	neighbors {1,2}, count 2	answer 0, best 2
cities 1,2	count 3 each	keep answer 0
city 3	neighbors {1,2}, count 2	equal count; return 3

Complexity Analysis

Time Complexity

O(n^3)

Space Complexity

O(n^2)

The n intermediate phases each examine n squared ordered pairs; initialization and counting cost O(n squared + edges). The matrix uses n squared entries. Java uses 1,000,000,000 as infinity and guards additions; any finite shortest path is at most 99 * 10,000 = 990,000, so finite sums fit int. Python and JavaScript use actual infinity.

Code

Solution.java

1import java.util.Arrays;2
3class Solution {4    public int findTheCity(int n, int[][] edges, int distanceThreshold) {5        final int INF = 1_000_000_000;6        int[][] dist = new int[n][n];7        for (int i = 0; i < n; i++) {8            Arrays.fill(dist[i], INF);9            dist[i][i] = 0;10        }11        for (int[] e : edges) dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];12        for (int k = 0; k < n; k++) {13            for (int i = 0; i < n; i++) {14                for (int j = 0; j < n; j++) {15                    if (dist[i][k] != INF && dist[k][j] != INF)16                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);17                }18            }19        }20        int answer = -1, best = n;21        for (int i = 0; i < n; i++) {22            int count = 0;23            for (int j = 0; j < n; j++)24                if (i != j && dist[i][j] <= distanceThreshold) count++;25            if (count <= best) { best = count; answer = i; }26        }27        return answer;28    }29}

Hints

Hint 1

Count reachable cities by shortest-path distance, not by direct roads.

Hint 2

For each potential intermediate k, compare the current i-to-j distance with i-to-k plus k-to-j.

Hint 3

Keep k outermost, exclude self when counting, and replace the winner on ties while scanning upward.

Edge Cases

Disconnected cities keep infinite distances; an isolated city can win.
A shortest distance equal to the threshold counts.
If every count ties, return n - 1, even when every count is zero.

Common Mistakes and Interview Tips

Putting the intermediate loop inside the source/destination loops breaks the phase invariant.
Counting roads rather than shortest routes misses cheaper indirect paths.
Initializing missing roads to zero makes unreachable cities appear nearby.
Replacing only on strictly smaller counts keeps the smallest tied index.

Key Takeaway

When answers depend on many pairs in a small graph, dynamic programming over allowed intermediates computes all shortest routes in one matrix.