1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance
Description
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 <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
All pairs
(fromi, toi)
are distinct.
ac1: Floyd-Warshall, O(V^3)
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // MAX_VALUE will cause overflow downstream
dist[i][i] = 0;
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int weight = edge[2];
dist[u][v] = weight;
dist[v][u] = weight;
}
// Standard Floyd-Warshall step: 1) iterate each V; 2) assume k is the mid point from i to j, relax dist[i][j];
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int res = -1;
int minReach = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int reach = 0;
for (int j = 0; j < n; j++) {
if (i == j) continue; // Same city
if (dist[i][j] <= distanceThreshold) {
reach++;
}
}
if (reach <= minReach) {
res = i;
minReach = reach;
}
}
return res;
}
}
// Floyd-Warshall, O(V^3) time, O(V^2) space. Tricky: use "Integer.MAX_VALUE / 2" to avoid overflow.
https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/discuss/491446/JavaC%2B%2B-Floyd-Warshall's-shortest-path-algorithm-Clean-code
ac2: Bellman-Ford, O(VEV)
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // MAX_VALUE will cause overflow downstream
dist[i][i] = 0;
}
for (int i = 0; i < n; i++) { // Do the following for each V to get a matrix of distance.
// Bellman-Ford: 1) iterate each V; 2) iterate each edge try to relax u-v, tricky: it's undirected graph, so do u->v and v->u.
for (int j = 0; j < n; j++) {
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int weight = edge[2];
if (dist[i][u] + weight < dist[i][v]) {
dist[i][v] = dist[i][u] + weight;
}
if (dist[i][v] + weight < dist[i][u]) {
dist[i][u] = dist[i][v] + weight;
}
}
}
}
int res = -1;
int minReach = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int reach = 0;
for (int j = 0; j < n; j++) {
if (i == j) continue; // Same city
if (dist[i][j] <= distanceThreshold) {
reach++;
}
}
if (reach <= minReach) {
res = i;
minReach = reach;
}
}
return res;
}
}
// Bellman-Ford, O(V*EV) time, O(V^2) space. E = V^2, so it's O(V^4), which is worse than Floyd-Warshall.
Shortest Path Faster Algorithm (SPFA) is an improvement of Bellman-Ford:
void spfa(int n, List<int[]>[] adj, int[] dist, int src) {
Deque<Integer> q = new ArrayDeque<>();
int[] updateTimes = new int[n];
q.add(src);
while (!q.isEmpty()) {
int u = q.removeFirst();
for (int[] next : adj[u]) {
int v = next[0];
int duv = next[1];
if (dist[v] > dist[u] + duv) {
dist[v] = dist[u] + duv;
updateTimes[v]++;
q.add(v);
if (updateTimes[v] > n) {System.out.println("wrong");}
}
}
}
}
ac3: Dijkstra, O(VElogV)
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // MAX_VALUE will cause overflow downstream
dist[i][i] = 0;
graph.put(i, new HashMap<>());
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int weight = edge[2];
graph.get(u).put(v, weight);
graph.get(v).put(u, weight);
}
for (int i = 0; i < n; i++) { // Do the following for each V to get a matrix of distance.
dijkstra(i, dist[i], graph);
}
int res = -1;
int minReach = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int reach = 0;
for (int j = 0; j < n; j++) {
if (i == j) continue; // Same city
if (dist[i][j] <= distanceThreshold) {
reach++;
}
}
if (reach <= minReach) {
res = i;
minReach = reach;
}
}
return res;
}
private void dijkstra(int src, int[] dist, Map<Integer, Map<Integer, Integer>> graph) {
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
q.offer(new int[]{src, 0});
while (!q.isEmpty()) {
int[] curr = q.poll();
int u = curr[0];
int srcToU = curr[1];
if (dist[u] < srcToU) continue; // src to u(dist[u]) is already smaller, no point to keep going.
for (int v : graph.get(u).keySet()) {
if (srcToU + graph.get(u).get(v) < dist[v]) {
dist[v] = srcToU + graph.get(u).get(v);
q.offer(new int[]{v, dist[v]});
}
}
}
}
}
// Dijkstra, O(V*ElogV) time, O(V^2) space. E = V^2, so it's O(V^3logV), which is worse than Floyd-Warshall.
// Tricky: you can use boolean[] visited to avoid loop, but it's better to rely on their weight, i.e. if (dist[u] < srcToU) continue;
Last updated
Was this helpful?