The city with the fewest neighbours within reach
There are n cities numbered 0 to n − 1. Each triple
[u, v, w] in edges is a two-way road of length w. A city can reach
another if the shortest route between them is at most distanceThreshold.
Return the city that can reach the fewest other cities. If several cities tie, return the one with the largest number.
Examples
| Input | Output | Why |
|---|---|---|
n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 | 3 | Cities 0 and 3 each reach two others; 3 is the larger number. |
n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 | 0 | City 0 reaches only city 1. |
n = 3, edges = [], distanceThreshold = 10 | 2 | No city reaches any other; the tie goes to the largest number. |
Constraints
- 2 ≤ n ≤ 100
- 0 ≤ edges.length ≤ n(n − 1)/2
- 1 ≤ w, distanceThreshold ≤ 10⁴
Hints
Hint 1
You need the shortest distance between every pair of cities. With n ≤ 100, Floyd–Warshall is the simplest way.
Hint 2
Roads are two-way: set both d[u][v] and d[v][u].
Hint 3
Scan cities in increasing order and replace the answer whenever a count is less than or equal to the best so far: that settles ties in favour of the larger number.
Where people lose marks
- Treating roads as one-way.
- Counting the city itself among its reachable neighbours.
- Breaking ties towards the smaller city number with a strict comparison.
Dry run on 4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6
Start: 0 on the diagonal, the edge weight where there is an edge, ∞ everywhere else. These are the shortest paths that use no intermediate node.
-
Step 2 / 6
k = 0: allow paths through node 0. Row 0 and column 0 (shaded) are read; nothing improves.
-
Step 3 / 6
k = 1: allow paths through node 1. Row 1 and column 1 (shaded) are read; 4 entries improve: 0→2 = 4, 0→3 = 7, 2→0 = 4, 3→0 = 7.
-
Step 4 / 6
k = 2: allow paths through node 2. Row 2 and column 2 (shaded) are read; 4 entries improve: 0→3 = 5, 1→3 = 2, 3→0 = 5, 3→1 = 2.
-
Step 5 / 6
k = 3: allow paths through node 3. Row 3 and column 3 (shaded) are read; nothing improves. Every node has been allowed as an intermediate: the matrix holds all shortest distances.
-
Step 6 / 6
With all distances known, count for each city the others within 4: city 0 reaches 2, city 1 reaches 3, city 2 reaches 3, city 3 reaches 2. The minimum is 2, shared by 0 and 3; the larger number wins, so the answer is 3.
How to think about it
The question needs the distance between every pair of cities, so compute all of them at once with Floyd–Warshall in O(n³), which for n = 100 is a million steps. Then, for each city, count the other cities at distance at most the threshold.
The tie rule is handled by the comparison: scanning from city 0 upwards and accepting a count that is less than or equal to the best so far leaves the largest-numbered city among those with the minimum.
Running Dijkstra from every city also works, at O(n · m log n), and is the better choice when n is large and the road network sparse.
Complexity. Time O(n³) · Space O(n²)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def find_the_city(n, edges, distance_threshold):
INF = float('inf')
d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
for u, v, w in edges:
d[u][v] = d[v][u] = min(d[u][v], w) # roads are two-way
for k in range(n):
for i in range(n):
if d[i][k] == INF:
continue
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, best_count = -1, INF
for city in range(n):
count = sum(1 for other in range(n) if other != city and d[city][other] <= distance_threshold)
if count <= best_count: # <= keeps the largest city on a tie
best, best_count = city, count
return best#include <algorithm>
#include <vector>
int solve(int n, const std::vector<std::vector<int>>& edges, int distanceThreshold) {
const int INF = 1 << 29;
std::vector<std::vector<int>> d(n, std::vector<int>(n, INF));
for (int i = 0; i < n; ++i) d[i][i] = 0;
for (const auto& e : edges) {
int w = std::min(d[e[0]][e[1]], e[2]);
d[e[0]][e[1]] = d[e[1]][e[0]] = w; // two-way roads
}
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]); // INF + INF still fits in int
int best = -1, bestCount = n + 1;
for (int city = 0; city < n; ++city) {
int count = 0;
for (int other = 0; other < n; ++other)
if (other != city && d[city][other] <= distanceThreshold) ++count;
if (count <= bestCount) { best = city; bestCount = count; }
}
return best;
}class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
final int INF = 1 << 29;
int[][] d = new int[n][n];
for (int i = 0; i < n; i++) {
java.util.Arrays.fill(d[i], INF);
d[i][i] = 0;
}
for (int[] e : edges) {
int w = Math.min(d[e[0]][e[1]], e[2]);
d[e[0]][e[1]] = w;
d[e[1]][e[0]] = w; // two-way roads
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
int best = -1, bestCount = n + 1;
for (int city = 0; city < n; city++) {
int count = 0;
for (int other = 0; other < n; other++)
if (other != city && d[city][other] <= distanceThreshold) count++;
if (count <= bestCount) { best = city; bestCount = count; }
}
return best;
}
}function findTheCity(n, edges, distanceThreshold) {
const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
for (const [u, v, w] of edges) d[u][v] = d[v][u] = Math.min(d[u][v], w); // two-way roads
for (let k = 0; k < n; k++)
for (let i = 0; i < n; i++) {
if (d[i][k] === Infinity) continue;
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 city = 0; city < n; city++) {
let count = 0;
for (let other = 0; other < n; other++) if (other !== city && d[city][other] <= distanceThreshold) count++;
if (count <= bestCount) { best = city; bestCount = count; } // <= : largest city wins a tie
}
return best;
}fn solve(n: i64, edges: &[[i64; 3]], distance_threshold: i64) -> i64 {
const INF: i64 = 1 << 40;
let n = n as usize;
let mut d = vec![vec![INF; n]; n];
for i in 0..n {
d[i][i] = 0;
}
for e in edges {
let (u, v) = (e[0] as usize, e[1] as usize);
let w = d[u][v].min(e[2]);
d[u][v] = w;
d[v][u] = w; // two-way roads
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
d[i][j] = d[i][j].min(d[i][k] + d[k][j]);
}
}
}
let mut best = -1i64;
let mut best_count = usize::MAX;
for city in 0..n {
let count = (0..n).filter(|&o| o != city && d[city][o] <= distance_threshold).count();
if count <= best_count { // <= : largest city wins a tie
best = city as i64;
best_count = count;
}
}
best
}import Data.List (foldl')
import qualified Data.Map.Strict as M
solve :: Int -> [[Int]] -> Int -> Int
solve n edges limit = snd (minimum [(count c, negate c) | c <- [0 .. n - 1]]) * (-1)
where
inf = 10 ^ 12 :: Int
start = M.fromListWith min ([((i, i), 0) | i <- [0 .. n - 1]]
++ concat [[((u, v), w), ((v, u), w)] | [u, v, w] <- edges])
look d i j = M.findWithDefault inf (i, j) d
final = foldl' (\d k -> M.fromList [((i, j), min (look d i j) (look d i k + look d k j))
| i <- [0 .. n - 1], j <- [0 .. n - 1]]) start [0 .. n - 1]
count c = length [o | o <- [0 .. n - 1], o /= c, look final c o <= limit]Variants to try
- Return the city that minimises the largest distance to any other (the centre of the graph).
- Roads close one at a time: answer the query after each closure.
- Make the threshold per city and return all cities whose count is below a limit.
Next problems
Distances between every pair of nodes
Return the matrix of shortest distances between every ordered pair of nodes, with −1 where no path exists.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem →Write a solution and run it against the real test table.
Keep going
Distances between every pair of nodes
Return the matrix of shortest distances between every ordered pair of nodes, with −1 where no path exists.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.