What is the brute force approach and complexity for Find the City With the Smallest Number of Neighbors at a Threshold Distance?

Run Bellman-Ford from each city, count the cities within the threshold, keep the fewest with time complexity O(N² · E) and space complexity O(N).

What is the optimal approach and complexity for Find the City With the Smallest Number of Neighbors at a Threshold Distance?

All-pairs distances in O(N³) with the middle city as the outer loop, then count per city with optimal time complexity O(N³) and space complexity O(N²).

How do you identify the pattern for Find the City With the Smallest Number of Neighbors at a Threshold Distance?

Look for key signals in the prompt: "for each city, count the cities within the threshold" indicates Distances between every pair are needed, not from one start. That points to all-pairs shortest paths.; "n ≤ 100" indicates N³ is about 10^6 steps, which is fast, so Floyd-Warshall is affordable.; "fewest, and the greatest number on a tie" indicates Compare with <= while scanning the cities in order, so the later city wins a tie..

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

Medium·LeetCode #1334Basic Anchor

LeetCode

Jump:

30-Second Mental ModelShortest Paths (weighted): All pairs (Floyd-Warshall)

Complexity:O(N² · E)→O(N³)

Key Insight

Start with d[i][j] = the road cost (0 on the diagonal, ∞ if there is no road). Then for each city k in turn, try k as a middle stop for every pair: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). After all the k rounds, d holds every shortest distance. Then count, for each city, the others within the threshold, and keep the fewest. On a tie keep the greater city.

Core Validity Invariant

After the round for k, d[i][j] is the shortest distance from i to j whose middle cities all lie in 0..k, for every pair (i, j).

Problem

There are n cities, numbered 0 to n − 1, joined by two-way roads. Each road is [a, b, w]: it links cities a and b, and travelling it costs w.

The distance between two cities is the cost of the cheapest route between them. For each city, count the other cities whose distance is at most distanceThreshold. Return the city with the fewest such cities. If several cities tie, return the one with the greatest number.

Input

n, edges (a list of [a, b, w]) and distanceThreshold.

Output

The number of the city with the fewest neighbours within the threshold. A tie goes to the greater city number.

Example 1

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

Output: 3

City 0 has 2 neighbours within 4 (cities 1 and 2). City 1 has 3, city 2 has 3, and city 3 has 2 (cities 1 and 2). Cities 0 and 3 tie at 2, so we return the greater number, 3.

Example 2

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

Output: 0

City 0 has only one neighbour within 2 (city 1, at distance 2). Every other city has at least two.

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.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The count for each city depends on its distance to every other city. Do I need one search per city, or can I get every distance in one go?
2.
If I run one shortest-path search from each city, how many searches do I run, and how many roads does each one scan?
3.
When a route passes through city k, which two shorter routes does it join? Do those two routes need to be finished first?
4.
Two cities can tie on the count. Which one does the statement pick, and how do I make the loop pick it without sorting?
5.
Which of the three loops has to be the outermost one, and what does that loop mean?

Brute force approach

Idea

For every city src, compute the shortest distance to every other city with Bellman-Ford: go over every road N − 1 times. Count the cities within the threshold. Keep the city with the smallest count, and on a tie keep the later one.

Thinking process

1
Bellman-Ford gives one row of distances, from one source. Do it for every source and we have the whole table, one row at a time.
2
Check it on example 1 from city 0. Start with dist = [0, ∞, ∞, ∞]. In the first pass over the roads: 0 → 1 gives 3, 1 → 2 gives 4, 1 → 3 gives 7, and 2 → 3 gives 5, which beats 7 (the roads are read in order, so the new values are used at once). The second pass changes nothing. So dist = [0, 3, 4, 5], and cities 1 (3) and 2 (4) are within 4. The count is 2.
3
Repeating that for all N cities costs N sources × (N − 1) passes × E roads, which is slow for N = 100.
4
The tests use N ≤ 7, so the brute force is fast enough to check against the optimal one.

Code & Implementation

brute.cpp

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        int city = -1, fewest = INT_MAX;
        for (int src = 0; src < n; src++) {
            vector<int> dist = fromSource(n, edges, src);
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != src && dist[j] <= distanceThreshold) count++;
            // <= : on a tie the later (larger) city replaces the earlier one.
            if (count <= fewest) { fewest = count; city = src; }
        }
        return city;
    }

private:
    // Bellman-Ford from src: n - 1 rounds over every edge. The roads are two-way,
    // so each edge is relaxed in both directions. No stop limit here, so updating in place is fine.
    vector<int> fromSource(int n, vector<vector<int>>& edges, int src) {
        const int INF = INT_MAX / 2;
        vector<int> dist(n, INF);
        dist[src] = 0;
        for (int round = 0; round < n - 1; round++)
            for (auto& e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
                if (dist[v] + w < dist[u]) dist[u] = dist[v] + w;
            }
        return dist;
    }
};

import java.util.*;

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int city = -1, fewest = Integer.MAX_VALUE;
        for (int src = 0; src < n; src++) {
            int[] dist = fromSource(n, edges, src);
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (j != src && dist[j] <= distanceThreshold) count++;
            }
            // <= : on a tie the later (larger) city replaces the earlier one.
            if (count <= fewest) {
                fewest = count;
                city = src;
            }
        }
        return city;
    }

    // Bellman-Ford from src: n - 1 rounds over every edge. The roads are two-way,
    // so each edge is relaxed in both directions. No stop limit here, so updating in place is fine.
    private int[] fromSource(int n, int[][] edges, int src) {
        final int INF = Integer.MAX_VALUE / 2;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 0; round < n - 1; round++) {
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
                if (dist[v] + w < dist[u]) dist[u] = dist[v] + w;
            }
        }
        return dist;
    }
}

from typing import List

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        city = -1
        fewest = float('inf')
        for src in range(n):
            dist = self._fromSource(n, edges, src)
            count = 0
            for j in range(n):
                if j != src and dist[j] <= distanceThreshold:
                    count += 1
            # <= : on a tie the later (larger) city replaces the earlier one.
            if count <= fewest:
                fewest = count
                city = src
        return city

    # Bellman-Ford from src: n - 1 rounds over every edge. The roads are two-way,
    # so each edge is relaxed in both directions. No stop limit here, so updating in place is fine.
    def _fromSource(self, n: int, edges: List[List[int]], src: int) -> List[int]:
        INF = float('inf')
        dist = [INF] * n
        dist[src] = 0
        for _ in range(n - 1):
            for u, v, w in edges:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                if dist[v] + w < dist[u]:
                    dist[u] = dist[v] + w
        return dist

export function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
    // Bellman-Ford from src: n - 1 rounds over every edge. The roads are two-way,
    // so each edge is relaxed in both directions. No stop limit here, so updating in place is fine.
    function fromSource(src: number): number[] {
        const INF = Infinity;
        const dist: number[] = new Array(n).fill(INF);
        dist[src] = 0;
        for (let round = 0; round < n - 1; round++) {
            for (const [u, v, w] of edges) {
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
                if (dist[v] + w < dist[u]) dist[u] = dist[v] + w;
            }
        }
        return dist;
    }

    let city = -1;
    let fewest = Infinity;
    for (let src = 0; src < n; src++) {
        const dist = fromSource(src);
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (j !== src && dist[j] <= distanceThreshold) count++;
        }
        // <= : on a tie the later (larger) city replaces the earlier one.
        if (count <= fewest) {
            fewest = count;
            city = src;
        }
    }
    return city;
}

Complexity

Time O(N² · E)Space O(N)

N is the number of cities and E the number of roads. Each source runs N − 1 passes over E roads, and there are N sources. With N = 100 and E at its maximum of 4950, that is about 5·10^7 relaxations. One distance array is reused for every source.

Optimized approach

Idea

Start from brute force

The brute force runs a full shortest-path search from every city. Each search solves the same kind of problem again, and the routes overlap: a route from i to j through k is built from the routes i → k and k → j.

Find the repeated work

Each search from a new city scans every road again, and the distances between other pairs are recomputed from scratch. Floyd-Warshall keeps one matrix, so each pair is improved in place instead.

Define the state — what variables do I need?

d[i][j]: The shortest distance found so far from city i to city j, using only middle cities 0..k. ∞ when no route is known yet.
k: The current middle city. It is the outermost loop, so each round lets one more city be used as a stop.
count[i]: How many other cities j have d[i][j] ≤ distanceThreshold. Read it after all the rounds.

Define validity

After the round for k, d[i][j] is the shortest distance from i to j whose middle cities all lie in 0..k, for every pair (i, j).

Define the transitions — when does each pointer move, and why is it safe?

Before any round

d[i][i] = 0; d[a][b] = d[b][a] = w for each road; every other entry is ∞

Before any middle city is tried, the only known routes are the direct roads and the trip from a city to itself.

Each k (outermost), each pair (i, j)

if d[i][k] + d[k][j] < d[i][j], set d[i][j] = d[i][k] + d[k][j]

Going i → k → j is a real route. It only uses middle cities 0..k, and it is kept when it is shorter than the best route found so far.

After all the k rounds

count each row with d[i][j] ≤ threshold, keep the fewest count, and on a tie keep the later city

Every pair now has its final distance, so each count is final too.

What does the current window add to the answer?

Each round adds one more city as a possible middle stop. After the last round the matrix is complete, and counting each row is one pass over N values.

Code & Implementation

optimal.cpp

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        const int INF = INT_MAX / 2;                  // /2 so INF + INF can't overflow
        vector<vector<int>> d(n, vector<int>(n, INF));
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (auto& e : edges) {                       // two-way roads
            d[e[0]][e[1]] = e[2];
            d[e[1]][e[0]] = e[2];
        }

        // Floyd-Warshall. k is the outer loop: after round k, d[i][j] is the best
        // path whose middle cities are all among 0..k.
        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];

        // Count the cities each city can reach within the threshold. Keep the fewest.
        int city = -1, fewest = INT_MAX;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && d[i][j] <= distanceThreshold) count++;
            // <= : on a tie the later (larger) city replaces the earlier one.
            if (count <= fewest) { fewest = count; city = i; }
        }
        return city;
    }
};

import java.util.*;

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        final int INF = Integer.MAX_VALUE / 2;                  // /2 so INF + INF can't overflow
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(d[i], INF);
            d[i][i] = 0;
        }
        for (int[] e : edges) {                                 // two-way roads
            d[e[0]][e[1]] = e[2];
            d[e[1]][e[0]] = e[2];
        }

        // Floyd-Warshall. k is the outer loop: after round k, d[i][j] is the best
        // path whose middle cities are all among 0..k.
        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];
                    }
                }
            }
        }

        // Count the cities each city can reach within the threshold. Keep the fewest.
        int city = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (j != i && d[i][j] <= distanceThreshold) count++;
            }
            // <= : on a tie the later (larger) city replaces the earlier one.
            if (count <= fewest) {
                fewest = count;
                city = i;
            }
        }
        return city;
    }
}

from typing import List

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        INF = float('inf')
        d = [[INF] * n for _ in range(n)]
        for i in range(n):
            d[i][i] = 0
        for u, v, w in edges:                       # two-way roads
            d[u][v] = w
            d[v][u] = w

        # Floyd-Warshall. k is the outer loop: after round k, d[i][j] is the best
        # path whose middle cities are all among 0..k.
        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]

        # Count the cities each city can reach within the threshold. Keep the fewest.
        city = -1
        fewest = float('inf')
        for i in range(n):
            count = 0
            for j in range(n):
                if j != i and d[i][j] <= distanceThreshold:
                    count += 1
            # <= : on a tie the later (larger) city replaces the earlier one.
            if count <= fewest:
                fewest = count
                city = i
        return city

export function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
    const INF = Infinity;
    const d: number[][] = Array.from({ length: n }, () => new Array(n).fill(INF));
    for (let i = 0; i < n; i++) d[i][i] = 0;
    for (const [u, v, w] of edges) {                       // two-way roads
        d[u][v] = w;
        d[v][u] = w;
    }

    // Floyd-Warshall. k is the outer loop: after round k, d[i][j] is the best
    // path whose middle cities are all among 0..k.
    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];
                }
            }
        }
    }

    // Count the cities each city can reach within the threshold. Keep the fewest.
    let city = -1;
    let fewest = Infinity;
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (j !== i && d[i][j] <= distanceThreshold) count++;
        }
        // <= : on a tie the later (larger) city replaces the earlier one.
        if (count <= fewest) {
            fewest = count;
            city = i;
        }
    }
    return city;
}

Complexity

Time O(N³)Space O(N²)

Three nested loops over N cities, then one count per row. The matrix holds N² distances. Running Dijkstra from every city is another option: O(N · E log N), which wins when the graph has few roads.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Run Bellman-Ford from each city, count the cities within the threshold, keep the fewest	O(N² · E)	O(N)
Optimal	All-pairs distances in O(N³) with the middle city as the outer loop, then count per city	O(N³)	O(N²)

Why does this belong to this pattern?

Clues in the problem statement

“for each city, count the cities within the threshold”Distances between every pair are needed, not from one start. That points to all-pairs shortest paths.
“n ≤ 100”N³ is about 10^6 steps, which is fast, so Floyd-Warshall is affordable.
“fewest, and the greatest number on a tie”Compare with <= while scanning the cities in order, so the later city wins a tie.

weighted roads+all pairs of cities+count within threshold per city+tie goes to the larger index→Shortest Paths (weighted): All pairs (Floyd-Warshall)

The distance is the same sum of road costs as in Dijkstra. What is new is that every pair is needed, so one run from one source is not enough. Floyd-Warshall gives all the distances in O(N³), and then one counting pass per city answers the question. The middle-city loop must be outermost: after round k, d[i][j] only covers middle cities 0..k, so putting the loop inside would give wrong distances.

Don't make this mistake

Breaking ties by the smaller index

✗ if (count < fewest) { fewest = count; city = i; }

✓ if (count <= fewest) { fewest = count; city = i; }

This is the pattern-confusion trap: the usual 'keep the first best' habit. On example 1 the counts are [2, 3, 3, 2]. With < the first city with 2 wins, which is city 0. The statement asks for the greater number, so the answer is 3.

Putting the k loop inside (wrong distances)

✗ for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) ...

✓ for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ...

Take the roads 0–1 (1), 1–3 (5) and 2–3 (3). The true distance from 0 to 2 is 9 (0 → 1 → 3 → 2). With i, j, k order, when i = 0 and j = 2 is checked, d[0][3] is still ∞, because it is only set later when j = 3 runs. So d[0][2] stays ∞. Example 1 still comes out right, which is why this bug is easy to miss.

Using < instead of <= for the threshold

✗ if (d[i][j] < distanceThreshold) count++;

✓ if (d[i][j] <= distanceThreshold) count++;

The statement says 'at most'. On example 1, d[0][2] = 4 is exactly the threshold. With <, city 0 has only 1 neighbour, so the answer becomes 0 instead of 3.

INF = INT_MAX, so the sum overflows

✗ const int INF = INT_MAX; // then d[i][k] + d[k][j] can overflow

✓ const int INF = INT_MAX / 2; // two INFs add up without overflowing

INT_MAX + INT_MAX does not fit in an int. In C++ that is undefined behaviour, and in practice the sum wraps to a negative number, which looks shorter than any real route. Halving INF keeps every sum safe.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Shortest Paths (Weighted) translate into production architectures and low-level memory mechanics.

LLD Architecture