Find the City With the Smallest Number of Neighbors at a Threshold Distance solution and explanation
Google
9 more videos on this problem
Find the City With the Smallest Number of Neighbors at a Threshold Distance - Leetcode 1334 - PythonNeetCodeIO · 15:07 · 13K views
Find the City With the Smallest Number of Neighbors at a Threshold Distance | 3 Ways | Leetcode 1334codestorywithMIK · 38:59 · 11K views
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance | Leetcode | DSAShashCode · 25:30 · 970 views
Solve LeetCode - 1334. Find the City With the Smallest Number of Neighbors at a Threshold DistanceMayur Programming Club · 24:43 · 289 views
[LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance개발자영맨(bluedawnstar) · 27:59 · 242 views
Find the City With the Smallest Number of Neighbors at a Threshold Distance - Leetcode 1334 - JavaCode With K5KC · 15:15 · 207 views
Day 33 | 1334. Find the City With the Smallest Number of Neighbors at a Threshold DistanceMaTb3a · 15:18 · 157 views
LeetCode 1334 - Find the City With Smallest Amount of Neighbors at a Threshold Distance - JavaAlpha-Code · 18:32 · 134 views
1334 find the city with smallest number of Neighbours at a threshold|Step-by-Step Solution|LeetCodeLeetQuest · 8:13 · 100 views
G-43. Find the City With the Smallest Number of Neighbours at a Threshold Distancetake U forward · 12:56 · 151K views
The problem
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- All pairs
(fromi, toi)are distinct.
Approach overview
Problem Overview: You are given n cities connected by weighted edges. A city can reach another if the shortest path distance is ≤ distanceThreshold. The goal is to return the city that can reach the smallest number of neighbors. If multiple cities tie, choose the one with the greatest index.
This is a classic all‑pairs shortest path problem. The key step is computing the minimum distance between every pair of cities, then counting how many are within the threshold for each city.
Approach 1: Floyd‑Warshall Algorithm (Time: O(n^3), Space: O(n^2))
Floyd‑Warshall computes shortest paths between every pair of nodes using dynamic programming. Initialize an n x n distance matrix with edge weights and set dist[i][i] = 0. Then iterate through each intermediate node k and update distances with dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After processing all intermediates, every cell contains the shortest path distance. Iterate through each city and count how many other cities have dist[i][j] ≤ distanceThreshold. Track the city with the smallest count, breaking ties by choosing the largest index. This method is straightforward and ideal when n is small (≤100), since the cubic runtime remains manageable.
This approach directly uses concepts from dynamic programming and graph shortest‑path relaxation.
Approach 2: Run Dijkstra from Every City (Time: O(n · (E log V)), Space: O(E + V))
Instead of computing all pairs at once, run Dijkstra’s algorithm starting from each city. Build an adjacency list for the graph, then use a min‑heap priority queue to repeatedly expand the smallest distance node. For each source city, compute shortest distances to all others while ignoring paths exceeding distanceThreshold. Count how many cities are reachable within the limit. Repeat this process for every city and maintain the minimum neighbor count with the required tie‑breaking rule.
This method scales better for sparse graphs where E is much smaller than n^2. It relies on standard shortest path techniques and a priority queue.
Recommended for interviews: Both approaches are acceptable. Floyd‑Warshall demonstrates clear understanding of all‑pairs shortest path and is often simpler to implement quickly. Running Dijkstra from each node shows stronger algorithmic awareness and performs better on sparse graphs. Mention both during discussion: the cubic dynamic programming solution first, then the repeated Dijkstra optimization.
Approach 1: Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is a classical dynamic programming algorithm to solve the all-pairs shortest path problem. It works well for graphs that have both weighted and unweighted edges. The algorithm iteratively updates the distance matrix for each possible intermediate node and provides the shortest distances between any two nodes.
The algorithm has a time complexity of O(n^3) and a space complexity of O(n^2), making it suitable for graphs with up to 100 nodes as given in the problem constraints.
def findTheCity(n, edges, distanceThreshold):
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, weight in edges:
dist[u][v] = weight
dist[v][u] = weight
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] < float('inf') and dist[k][j] < float('inf'):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
min_city = -1
min_neighbors = float('inf')
for i in range(n):
count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
if count <= min_neighbors:
min_neighbors = count
min_city = i
return min_city
n = 4
edges = [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]]
distanceThreshold = 4
print(findTheCity(n, edges, distanceThreshold))import java.util.Arrays;
public 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);
dist[i][i] = 0;
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1], weight = edge[2];
dist[u][v] = weight;
dist[v][u] = weight;
}
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] < Integer.MAX_VALUE && dist[k][j] < Integer.MAX_VALUE
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int city = -1, minReachableCities = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int reachableCities = 0;
for (int j = 0; j < n; j++) {
if (i != j && dist[i][j] <= distanceThreshold) {
++reachableCities;
}
}
if (reachableCities <= minReachableCities) {
minReachableCities = reachableCities;
city = i;
}
}
return city;
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 4;
int[][] edges = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
int distanceThreshold = 4;
System.out.println(solution.findTheCity(n, edges, distanceThreshold));
}
}#include <iostream>
#include <vector>
#include <climits>
int findTheCity(int n, std::vector<std::vector<int>>& edges, int distanceThreshold) {
std::vector<std::vector<int>> dist(n, std::vector<int>(n, INT_MAX));
for (int i = 0; i < n; ++i) dist[i][i] = 0;
for (auto& edge : edges) {
int u = edge[0], v = edge[1], weight = edge[2];
dist[u][v] = weight;
dist[v][u] = weight;
}
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] < INT_MAX && dist[k][j] < INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int city = -1, minReachableCities = INT_MAX;
for (int i = 0; i < n; ++i) {
int reachableCities = 0;
for (int j = 0; j < n; ++j) {
if (i != j && dist[i][j] <= distanceThreshold) {
++reachableCities;
}
}
if (reachableCities <= minReachableCities) {
minReachableCities = reachableCities;
city = i;
}
}
return city;
}
int main() {
int n = 4;
std::vector<std::vector<int>> edges = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
int distanceThreshold = 4;
std::cout << findTheCity(n, edges, distanceThreshold) << std::endl;
return 0;
}function findTheCity(n, edges, distanceThreshold) {
const dist = Array.from({ length: n }, () => Array(n).fill(Infinity));
for (let i = 0; i < n; ++i) dist[i][i] = 0;
for (const [u, v, weight] of edges) {
dist[u][v] = weight;
dist[v][u] = weight;
}
for (let k = 0; k < n; ++k) {
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (dist[i][k] < Infinity && dist[k][j] < Infinity) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
let minCity = -1, minNeighbors = Infinity;
for (let i = 0; i < n; ++i) {
let count = 0;
for (let j = 0; j < n; ++j) {
if (i !== j && dist[i][j] <= distanceThreshold) {
++count;
}
}
if (count <= minNeighbors) {
minNeighbors = count;
minCity = i;
}
}
return minCity;
}
const n = 4;
const edges = [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]];
const distanceThreshold = 4;
console.log(findTheCity(n, edges, distanceThreshold));#include <stdio.h>
#include <limits.h>
#define MAX 100
void findCity(int n, int edges[][3], int edgesSize, int distanceThreshold) {
int dist[MAX][MAX];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < edgesSize; ++i) {
int from = edges[i][0], to = edges[i][1], weight = edges[i][2];
dist[from][to] = weight;
dist[to][from] = weight;
}
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] != INT_MAX && dist[k][j] != INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int minCity = -1, minNeighbors = INT_MAX;
for (int i = 0; i < n; ++i) {
int count = 0;
for (int j = 0; j < n; ++j) {
if (i != j && dist[i][j] <= distanceThreshold) {
count++;
}
}
if (count <= minNeighbors) {
minNeighbors = count;
minCity = i;
}
}
printf("%d\n", minCity);
}using System;
public class Solution {
public int FindTheCity(int n, int[][] edges, int distanceThreshold) {
int[,] dist = new int[n, n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i, j] = i == j ? 0 : int.MaxValue;
foreach (var edge in edges) {
int u = edge[0], v = edge[1], weight = edge[2];
dist[u, v] = weight;
dist[v, u] = weight;
}
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] < int.MaxValue && dist[k, j] < int.MaxValue
&& dist[i, k] + dist[k, j] < dist[i, j]) {
dist[i, j] = dist[i, k] + dist[k, j];
}
int city = -1, minReachableCities = int.MaxValue;
for (int i = 0; i < n; i++) {
int reachableCities = 0;
for (int j = 0; j < n; j++) {
if (i != j && dist[i, j] <= distanceThreshold) {
++reachableCities;
}
}
if (reachableCities <= minReachableCities) {
minReachableCities = reachableCities;
city = i;
}
}
return city;
}
public static void Main() {
var solution = new Solution();
int n = 4;
int[][] edges = { new [] {0, 1, 3}, new [] {1, 2, 1}, new [] {1, 3, 4}, new [] {2, 3, 1} };
int distanceThreshold = 4;
Console.WriteLine(solution.FindTheCity(n, edges, distanceThreshold));
}
}This Python solution calculates all pairs shortest paths using Floyd-Warshall, then counts neighbors reachable under a defined threshold for each city. It returns the city with the minimal count or higher index in case of ties.
Time Complexity: O(n^3), where n is the number of cities.
Space Complexity: O(n^2) for the distance matrix.
Approach 2: Dijkstra's Algorithm
Dijkstra's Algorithm can be employed to find the shortest path from one city to another in a graph with non-negative weights. We can utilize this algorithm to determine the shortest distance from every city to all other cities consecutively, assessing the count of reachable cities within the threshold afterward.
import heapq
def findTheCity(n, edges, distanceThreshold):
graph = [[] for _ in range(n)]
for u, v, weight in edges:
graph[u].append((v, weight))
graph[v].append((u, weight))
def dijkstra(source):
dist = [float('inf')] * n
dist[source] = 0
minHeap = [(0, source)]
while minHeap:
curDist, u = heapq.heappop(minHeap)
if curDist > dist[u]:
continue
for v, length in graph[u]:
if dist[u] + length < dist[v]:
dist[v] = dist[u] + length
heapq.heappush(minHeap, (dist[v], v))
return dist
minCity = -1
minNeighbors = float('inf')
for i in range(n):
dist = dijkstra(i)
count = sum(1 for j in range(n) if i != j and dist[j] <= distanceThreshold)
if count <= minNeighbors:
minNeighbors = count
minCity = i
return minCity
n = 4
edges = [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]]
distanceThreshold = 4
print(findTheCity(n, edges, distanceThreshold))import java.util.*;
public class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
List<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] edge : edges) {
graph[edge[0]].add(new int[]{edge[1], edge[2]});
graph[edge[1]].add(new int[]{edge[0], edge[2]});
}
int minCity = -1, minNeighbors = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[i] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{i, 0});
while (!pq.isEmpty()) {
int[] pair = pq.poll();
int u = pair[0], distanceU = pair[1];
if (distanceU > dist[u]) continue;
for (int[] neighbor : graph[u]) {
int v = neighbor[0], weightUV = neighbor[1];
if (dist[u] + weightUV < dist[v]) {
dist[v] = dist[u] + weightUV;
pq.offer(new int[]{v, dist[v]});
}
}
}
int count = 0;
for (int j = 0; j < n; j++) {
if (i != j && dist[j] <= distanceThreshold) count++;
}
if (count <= minNeighbors) {
minNeighbors = count;
minCity = i;
}
}
return minCity;
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 4;
int[][] edges = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
int distanceThreshold = 4;
System.out.println(solution.findTheCity(n, edges, distanceThreshold));
}
}#include <iostream>
#include <vector>
#include <queue>
#include <climits>
int findTheCity(int n, std::vector<std::vector<int>>& edges, int distanceThreshold) {
std::vector<std::pair<int, int>> adj[n];
for (const auto& edge : edges) {
adj[edge[0]].emplace_back(edge[1], edge[2]);
adj[edge[1]].emplace_back(edge[0], edge[2]);
}
int minCity = -1, minNeighbors = INT_MAX;
for (int i = 0; i < n; ++i) {
std::vector<int> dist(n, INT_MAX);
dist[i] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
pq.emplace(0, i);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.emplace(dist[v], v);
}
}
}
int count = 0;
for (int j = 0; j < n; ++j) {
if (i != j && dist[j] <= distanceThreshold) {
++count;
}
}
if (count <= minNeighbors) {
minNeighbors = count;
minCity = i;
}
}
return minCity;
}
int main() {
int n = 4;
std::vector<std::vector<int>> edges = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
int distanceThreshold = 4;
std::cout << findTheCity(n, edges, distanceThreshold) << std::endl;
return 0;
}function findTheCity(n, edges, distanceThreshold) {
const graph = Array.from({ length: n }, () => []);
for (let [u, v, weight] of edges) {
graph[u].push([v, weight]);
graph[v].push([u, weight]);
}
function dijkstra(src) {
const dist = Array(n).fill(Infinity);
dist[src] = 0;
const minHeap = [[0, src]];
while (minHeap.length > 0) {
minHeap.sort((a, b) => a[0] - b[0]);
const [curDist, u] = minHeap.shift();
if (curDist > dist[u]) continue;
for (const [v, length] of graph[u]) {
if (dist[u] + length < dist[v]) {
dist[v] = dist[u] + length;
minHeap.push([dist[v], v]);
}
}
}
return dist;
}
let minCity = -1;
let minNeighbors = Infinity;
for (let i = 0; i < n; i++) {
const dist = dijkstra(i);
const count = dist.reduce((acc, d, j) => acc + ((i !== j && d <= distanceThreshold) ? 1 : 0), 0);
if (count <= minNeighbors) {
minNeighbors = count;
minCity = i;
}
}
return minCity;
}
const n = 4;
const edges = [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]];
const distanceThreshold = 4;
console.log(findTheCity(n, edges, distanceThreshold));#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define MAX 100
int minDistance(int dist[], bool sptSet[], int n) {
int min = INT_MAX, min_index;
for (int v = 0; v < n; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void dijkstra(int graph[MAX][MAX], int src, int dist[], int n) {
bool sptSet[n];
for (int i = 0; i < n; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < n - 1; count++) {
int u = minDistance(dist, sptSet, n);
sptSet[u] = true;
for (int v = 0; v < n; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
}
int findTheCity(int n, int edges[][3], int edgesSize, int distanceThreshold) {
int graph[MAX][MAX] = {0};
for (int i = 0; i < edgesSize; ++i) {
int from = edges[i][0], to = edges[i][1], weight = edges[i][2];
graph[from][to] = weight;
graph[to][from] = weight;
}
int minCity = -1, minNeighbors = INT_MAX;
for (int i = 0; i < n; ++i) {
int dist[MAX];
dijkstra(graph, i, dist, n);
int count = 0;
for (int j = 0; j < n; ++j) {
if (i != j && dist[j] <= distanceThreshold) {
count++;
}
}
if (count <= minNeighbors) {
minNeighbors = count;
minCity = i;
}
}
return minCity;
}
int main() {
int n = 4;
int edges[][3] = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
int distanceThreshold = 4;
printf("%d\n", findTheCity(n, edges, 4, distanceThreshold));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int FindTheCity(int n, int[][] edges, int distanceThreshold) {
List<Tuple<int, int>>[] graph = new List<Tuple<int, int>>[n];
for (int i = 0; i < n; i++)
graph[i] = new List<Tuple<int, int>>();
foreach (var edge in edges) {
graph[edge[0]].Add(Tuple.Create(edge[1], edge[2]));
graph[edge[1]].Add(Tuple.Create(edge[0], edge[2]));
}
int minCity = -1, minNeighbors = int.MaxValue;
for (int i = 0; i < n; i++) {
int[] dist = new int[n];
Array.Fill(dist, int.MaxValue);
dist[i] = 0;
var pq = new SortedSet<Tuple<int, int>> { Tuple.Create(0, i) };
while (pq.Count > 0) {
var min = pq.Min;
pq.Remove(min);
int u = min.Item2, curDist = min.Item1;
if (curDist > dist[u]) continue;
foreach (var neighbor in graph[u]) {
int v = neighbor.Item1, weight = neighbor.Item2;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.Add(Tuple.Create(dist[v], v));
}
}
}
int count = 0;
for (int j = 0; j < n; j++)
if (i != j && dist[j] <= distanceThreshold)
count++;
if (count <= minNeighbors) {
minNeighbors = count;
minCity = i;
}
}
return minCity;
}
public static void Main() {
var solution = new Solution();
int n = 4;
int[][] edges = { new [] {0, 1, 3}, new [] {1, 2, 1}, new [] {1, 3, 4}, new [] {2, 3, 1} };
int distanceThreshold = 4;
Console.WriteLine(solution.FindTheCity(n, edges, distanceThreshold));
}
}This Python solution utilizes Dijkstra's algorithm by setting up a priority queue to process nodes, ensuring efficient shortest path computations for each city and consequently identifies cities based on the neighbors' criteria.
Time Complexity: O(n^2 log n) due to queue operations.
Space Complexity: O(n^2) to maintain adjacency list.
Approach 3: Default Approach
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Floyd-Warshall Algorithm | Time Complexity: |
| Dijkstra's Algorithm | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Floyd-Warshall Algorithm | O(n^3) | O(n^2) | Best when the graph is small and you want a simple all-pairs shortest path solution |
| Dijkstra from Each Node | O(n · (E log V)) | O(E + V) | Preferred for sparse graphs where edges are far fewer than n^2 |
Frequently asked questions
Is Find the City With the Smallest Number of Neighbors at a Threshold Distance easy or hard?
The problem is rated Medium difficulty on LeetCode. The main challenge is recognizing it as a shortest‑path problem and choosing the right algorithm. Once you apply Floyd‑Warshall or Dijkstra correctly, the remaining logic is counting reachable cities and applying the tie‑breaking rule.
Find the City With the Smallest Number of Neighbors at a Threshold Distance Python/Java solution
Most solutions implement Floyd‑Warshall or repeated Dijkstra. Python typically uses lists for the distance matrix or adjacency list and the heapq module for the priority queue. Java solutions often use arrays for distances and PriorityQueue for Dijkstra's algorithm.
How to solve Find the City With the Smallest Number of Neighbors at a Threshold Distance in O(n^3)?
Use the Floyd‑Warshall algorithm. Initialize a distance matrix with edge weights and repeatedly relax distances through intermediate nodes using dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After computing all shortest paths, count how many cities each city can reach within the distance threshold and select the city with the smallest count.
What is the best approach for Find the City With the Smallest Number of Neighbors at a Threshold Distance?
Two common approaches solve this problem: Floyd‑Warshall and running Dijkstra from every node. Floyd‑Warshall computes all‑pairs shortest paths in O(n^3) time and is simple to implement. Repeated Dijkstra runs in O(n · (E log V)) and performs better for sparse graphs. Interviewers often accept either solution.
Is Find the City With the Smallest Number of Neighbors at a Threshold Distance asked at Google/Amazon/Meta?
Graph shortest‑path problems similar to this one frequently appear in interviews at companies like Amazon, Google, and Meta. The question tests understanding of graph representations, shortest path algorithms such as Dijkstra, and all‑pairs techniques like Floyd‑Warshall.
What data structure is used in Find the City With the Smallest Number of Neighbors at a Threshold Distance?
The problem uses graph data structures. Floyd‑Warshall relies on a 2D distance matrix to store shortest paths between all city pairs. The Dijkstra approach uses an adjacency list representation of the graph along with a min‑heap priority queue for efficient shortest path expansion.
What is the time complexity of Find the City With the Smallest Number of Neighbors at a Threshold Distance?
The Floyd‑Warshall solution runs in O(n^3) time with O(n^2) space because it updates distances between every pair of cities through each intermediate node. Running Dijkstra from each city has time complexity O(n · (E log V)) with O(E + V) space using an adjacency list and priority queue.