Find the City With the Smallest Number of Neighbors at a Threshold Distance
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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Floyd–Warshall | O(n³) | O(n²) |
| Dijkstra from every city | O(n · E log n) | O(n + E) |
1Floyd–Warshall
O(n³)O(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.
- Initialise dist with edges, 0 on the diagonal, INF elsewhere.
- For k, i, j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
- Pick the city with the fewest reachable cities, taking the larger index on ties.
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;
}
}class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
INF = (2**31 - 1) // 2
d = [[INF] * n for _ in range(n)]
for i in range(n):
d[i][i] = 0
for e in edges:
d[e[0]][e[1]] = e[2]
d[e[1]][e[0]] = e[2]
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, bestCount = -1, math.inf
for i in range(n):
c = 0
for j in range(n):
if i != j and d[i][j] <= distanceThreshold:
c += 1
if c <= bestCount:
bestCount = c
best = i
return bestclass Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
int INF = INT_MAX / 2;
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, bestCount = INT_MAX;
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;
}
};function findTheCity(n, edges, distanceThreshold) {
const INF = Math.floor(2147483647 / 2);
const d = Array.from({ length: n }, () => new Array(n).fill(INF));
for (let i = 0; i < n; i++) d[i][i] = 0;
for (const e of edges) { d[e[0]][e[1]] = e[2]; d[e[1]][e[0]] = e[2]; }
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, bestCount = Infinity;
for (let i = 0; i < n; i++) {
let c = 0;
for (let 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
O(n · E log n)O(n + E)Run Dijkstra from each city, count the cities within the threshold, and keep the best. Faster than Floyd–Warshall on sparse graphs.
- For each source: Dijkstra; count dist <= threshold.
- Choose the smallest count, largest index on ties.
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;
}
}class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
adj = [[] for _ in range(n)]
for e in edges:
adj[e[0]].append((e[1], e[2]))
adj[e[1]].append((e[0], e[2]))
best, bestCount = -1, math.inf
for s in range(n):
dist = [math.inf] * n
dist[s] = 0
pq = [(0, s)]
while pq:
cur = heapq.heappop(pq)
if cur[0] > dist[cur[1]]:
continue
for e in adj[cur[1]]:
nd = cur[0] + e[1]
if nd < dist[e[0]]:
dist[e[0]] = nd
heapq.heappush(pq, (nd, e[0]))
c = 0
for j in range(n):
if j != s and dist[j] <= distanceThreshold:
c += 1
if c <= bestCount:
bestCount = c
best = s
return bestclass Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
vector<vector<pair<int, int>>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back({ e[1], e[2] });
adj[e[1]].push_back({ e[0], e[2] });
}
int best = -1, bestCount = INT_MAX;
for (int s = 0; s < n; s++) {
vector<int> dist(n, INT_MAX);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, s });
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
if (cur.first > dist[cur.second]) continue;
for (auto& e : adj[cur.second]) {
int nd = cur.first + e.second;
if (nd < dist[e.first]) { dist[e.first] = nd; pq.push({ nd, e.first }); }
}
}
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;
}
};function findTheCity(n, edges, distanceThreshold) {
const adj = Array.from({ length: n }, () => []);
for (const e of edges) {
adj[e[0]].push([e[1], e[2]]);
adj[e[1]].push([e[0], e[2]]);
}
let best = -1, bestCount = Infinity;
for (let s = 0; s < n; s++) {
const dist = new Array(n).fill(Infinity);
dist[s] = 0;
const pq = [];
const push = (x) => {
pq.push(x);
let i = pq.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (pq[p][0] <= pq[i][0]) break;
[pq[p], pq[i]] = [pq[i], pq[p]];
i = p;
}
};
const pop = () => {
const top = pq[0];
const last = pq.pop();
if (pq.length > 0) {
pq[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < pq.length && pq[l][0] < pq[m][0]) m = l;
if (r < pq.length && pq[r][0] < pq[m][0]) m = r;
if (m === i) break;
[pq[m], pq[i]] = [pq[i], pq[m]];
i = m;
}
}
return top;
};
push([0, s]);
while (pq.length > 0) {
const cur = pop();
if (cur[0] > dist[cur[1]]) continue;
for (const e of adj[cur[1]]) {
const nd = cur[0] + e[1];
if (nd < dist[e[0]]) { dist[e[0]] = nd; push([nd, e[0]]); }
}
}
let c = 0;
for (let 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, Cheapest Flights Within K Stops, Swim in Rising Water.
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.