Move from brute-force thinking to an efficient approach using dynamic programming strategy.
There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.
Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.
Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.
Example 1:
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 Output: 3 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 4 for each city are: City 0 -> [City 1, City 2] City 1 -> [City 0, City 2, City 3] City 2 -> [City 0, City 1, City 3] City 3 -> [City 1, City 2] Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.
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 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 2 for each city are: City 0 -> [City 1] City 1 -> [City 0, City 4] City 2 -> [City 3, City 4] City 3 -> [City 2, City 4] City 4 -> [City 1, City 2, City 3] The city 0 has 1 neighboring city at a distanceThreshold = 2.
Constraints:
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= fromi < toi < n1 <= weighti, distanceThreshold <= 10^4(fromi, toi) are distinct.Problem summary: There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold. Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number. Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
4 [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] 4
5 [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]] 2
second-minimum-time-to-reach-destination)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance
class Solution {
private int n;
private int[][] g;
private int[] dist;
private boolean[] vis;
private final int inf = 1 << 30;
private int distanceThreshold;
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
this.n = n;
this.distanceThreshold = distanceThreshold;
g = new int[n][n];
dist = new int[n];
vis = new boolean[n];
for (var e : g) {
Arrays.fill(e, inf);
}
for (var e : edges) {
int f = e[0], t = e[1], w = e[2];
g[f][t] = w;
g[t][f] = w;
}
int ans = n, cnt = inf;
for (int i = n - 1; i >= 0; --i) {
int t = dijkstra(i);
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
private int dijkstra(int u) {
Arrays.fill(dist, inf);
Arrays.fill(vis, false);
dist[u] = 0;
for (int i = 0; i < n; ++i) {
int k = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (k == -1 || dist[k] > dist[j])) {
k = j;
}
}
vis[k] = true;
for (int j = 0; j < n; ++j) {
dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
}
}
int cnt = 0;
for (int d : dist) {
if (d <= distanceThreshold) {
++cnt;
}
}
return cnt;
}
}
// Accepted solution for LeetCode #1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance
func findTheCity(n int, edges [][]int, distanceThreshold int) int {
g := make([][]int, n)
dist := make([]int, n)
vis := make([]bool, n)
const inf int = 1e7
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = inf
}
}
for _, e := range edges {
f, t, w := e[0], e[1], e[2]
g[f][t], g[t][f] = w, w
}
dijkstra := func(u int) (cnt int) {
for i := range vis {
vis[i] = false
dist[i] = inf
}
dist[u] = 0
for i := 0; i < n; i++ {
k := -1
for j := 0; j < n; j++ {
if !vis[j] && (k == -1 || dist[j] < dist[k]) {
k = j
}
}
vis[k] = true
for j := 0; j < n; j++ {
dist[j] = min(dist[j], dist[k]+g[k][j])
}
}
for _, d := range dist {
if d <= distanceThreshold {
cnt++
}
}
return
}
ans, cnt := n, inf
for i := n - 1; i >= 0; i-- {
if t := dijkstra(i); t < cnt {
cnt = t
ans = i
}
}
return ans
}
# Accepted solution for LeetCode #1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance
class Solution:
def findTheCity(
self, n: int, edges: List[List[int]], distanceThreshold: int
) -> int:
def dijkstra(u: int) -> int:
dist = [inf] * n
dist[u] = 0
vis = [False] * n
for _ in range(n):
k = -1
for j in range(n):
if not vis[j] and (k == -1 or dist[k] > dist[j]):
k = j
vis[k] = True
for j in range(n):
# dist[j] = min(dist[j], dist[k] + g[k][j])
if dist[k] + g[k][j] < dist[j]:
dist[j] = dist[k] + g[k][j]
return sum(d <= distanceThreshold for d in dist)
g = [[inf] * n for _ in range(n)]
for f, t, w in edges:
g[f][t] = g[t][f] = w
ans, cnt = n, inf
for i in range(n - 1, -1, -1):
if (t := dijkstra(i)) < cnt:
cnt, ans = t, i
return ans
// Accepted solution for LeetCode #1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance
struct Solution;
impl Solution {
fn find_the_city(n: i32, edges: Vec<Vec<i32>>, distance_threshold: i32) -> i32 {
let n = n as usize;
let mut dist = vec![vec![std::i32::MAX >> 2; n]; n];
for i in 0..n {
dist[i][i] = 0;
}
for e in edges {
let i = e[0] as usize;
let j = e[1] as usize;
let d = e[2];
dist[i][j] = d;
dist[j][i] = d;
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]);
}
}
}
let mut min = (n, 0);
for i in 0..n {
let count = dist[i].iter().filter(|&&d| d <= distance_threshold).count() - 1;
if count <= min.0 {
min = (count, i);
}
}
min.1 as i32
}
}
#[test]
fn test() {
let n = 4;
let edges = vec_vec_i32![[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]];
let distance_threshold = 4;
let res = 3;
assert_eq!(Solution::find_the_city(n, edges, distance_threshold), res);
let n = 5;
let edges = vec_vec_i32![
[0, 1, 2],
[0, 4, 8],
[1, 2, 3],
[1, 4, 2],
[2, 3, 1],
[3, 4, 1]
];
let distance_threshold = 2;
let res = 0;
assert_eq!(Solution::find_the_city(n, edges, distance_threshold), res);
}
// Accepted solution for LeetCode #1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance
function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
const dist: number[] = Array(n).fill(Infinity);
const vis: boolean[] = Array(n).fill(false);
for (const [f, t, w] of edges) {
g[f][t] = g[t][f] = w;
}
const dijkstra = (u: number): number => {
dist.fill(Infinity);
vis.fill(false);
dist[u] = 0;
for (let i = 0; i < n; ++i) {
let k = -1;
for (let j = 0; j < n; ++j) {
if (!vis[j] && (k === -1 || dist[j] < dist[k])) {
k = j;
}
}
vis[k] = true;
for (let j = 0; j < n; ++j) {
dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
}
}
return dist.filter(d => d <= distanceThreshold).length;
};
let ans = n;
let cnt = Infinity;
for (let i = n - 1; i >= 0; --i) {
const t = dijkstra(i);
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.