Start practising

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

Medium Graphs Dijkstra Original on LeetCode

Find the City With the Smallest Number of Neighbors at a Threshold Distance is a medium graphs problem solved with the dijkstra pattern. The best approach, dijkstra from every city, runs in O(n · E log n) time and O(n + E) space. Below are 2 approaches in Java, from floyd–warshall up.

Problem

There are n cities joined by weighted, undirected roads. Find the city that can reach the fewest other cities within distanceThreshold (along shortest paths). If several cities tie, return the one with the largest index.

Examples

Example 1

Input
n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output
3
Why
Cities 0 and 3 each reach 2 others within 4; on a tie, return the larger index.

Example 2

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

Constraints

  • 2 <= n <= 100; undirected weighted edges; weights 1 to 10^4.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Floyd–WarshallO(n³)O(n²)
Dijkstra from every cityO(n · E log n)O(n + E)

1Floyd–Warshall

TimeO(n³)
SpaceO(n²)

dist[i][j] starts as the direct edge weight. For each intermediate city k, try to shorten every pair through k. Then count, for each city, how many others are within the threshold.

  1. Initialise dist with edges, 0 on the diagonal, INF elsewhere.
  2. For k, i, j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  3. Pick the city with the fewest reachable cities, taking the larger index on ties.
Java
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] d = new int[n][n];
        for (int[] row : d) Arrays.fill(row, 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, bestCount = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int c = 0;
            for (int j = 0; j < n; j++) if (i != j && d[i][j] <= distanceThreshold) c++;
            if (c <= bestCount) { bestCount = c; best = i; }
        }
        return best;
    }
}

2Dijkstra from every city

TimeO(n · E log n)
SpaceO(n + E)

Run Dijkstra from each city, count the cities within the threshold, and keep the best. Faster than Floyd–Warshall on sparse graphs.

  1. For each source: Dijkstra; count dist <= threshold.
  2. Choose the smallest count, largest index on ties.
Java
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[] { e[1], e[2] });
            adj.get(e[1]).add(new int[] { e[0], e[2] });
        }
        int best = -1, bestCount = Integer.MAX_VALUE;
        for (int s = 0; s < n; s++) {
            int[] dist = new int[n];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[s] = 0;
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
            pq.add(new int[] { 0, s });
            while (!pq.isEmpty()) {
                int[] cur = pq.poll();
                if (cur[0] > dist[cur[1]]) continue;
                for (int[] e : adj.get(cur[1])) {
                    int nd = cur[0] + e[1];
                    if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.add(new int[] { nd, e[0] }); }
                }
            }
            int c = 0;
            for (int j = 0; j < n; j++) if (j != s && dist[j] <= distanceThreshold) c++;
            if (c <= bestCount) { bestCount = c; best = s; }
        }
        return best;
    }
}

Edge cases to test

  • Ties (return the largest city index)
  • Cities reaching nobody

Hints

Hint 1

You need shortest distances between every pair of cities: run Dijkstra from each city, or Floyd–Warshall once.

FAQ

What is the best time complexity for Find the City With the Smallest Number of Neighbors at a Threshold Distance?

Dijkstra from every city runs in O(n · E log n) time and O(n + E) extra space.

Which pattern does Find the City With the Smallest Number of Neighbors at a Threshold Distance use?

It is a graphs problem that uses the dijkstra pattern. Other problems with the same pattern: Network Delay Time.

Is there a brute force solution for Find the City With the Smallest Number of Neighbors at a Threshold Distance?

Yes. Floyd–Warshall takes O(n³) time and O(n²) space. dist[i][j] starts as the direct edge weight.

Which edge cases should I test for Find the City With the Smallest Number of Neighbors at a Threshold Distance?

Ties (return the largest city index); Cities reaching nobody.