NeetCode #640LC-1334MediumAdvanced Graphs
← Back to All Problems#640 · #1334 · Find the City With the Smallest Number of Neighbors at a Threshold Distance(阈值距离内邻居最少的城市)
📌 Problem Statement & Constraints
There are
n cities with edges[i] = [from, to, weight]. Given distanceThreshold, return the city with the smallest number of reachable cities within the threshold (excluding itself); ties break by the largest index. Constraints: 2 <= n <= 100, 1 <= edges.length <= n * (n - 1) / 2.💡 Core Algorithmic Approaches
- All-pairs shortest paths are needed, and
n <= 100makes Floyd-Warshall ideal. - After the O(n^3) DP, each row gives the distances from one city.
- Count the entries at most
distanceThreshold, and pick the minimum count with the largest index on ties. - Dijkstra from each city would also work, at O(n * E log V).
💻 Benchmark Python3 Implementation
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
INF = float("inf")
d = [[INF] * n for _ in range(n)]
for i in range(n):
d[i][i] = 0
for u, v, w in edges:
d[u][v] = d[v][u] = min(d[u][v], w) # keep the smallest parallel edge
# Floyd-Warshall
for k in range(n):
for i in range(n):
if d[i][k] == INF:
continue # prune unreachable
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_city, best_cnt = -1, n + 1
for i in range(n):
cnt = sum(1 for j in range(n) if i != j and d[i][j] <= distanceThreshold)
if cnt <= best_cnt: # '<=' -> the largest index wins ties
best_cnt = cnt
best_city = i
return best_city⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^3) for Floyd-Warshall, plus O(n^2) for the counting.
💾 Space Complexity
O(n^2) for the distance matrix.
⚠️ Interview Pitfalls & Follow-ups
- Using
<=vs<for the tie-break: the problem wants the largest index, so<=is correct when iterating ascending. - Forgetting to initialise the diagonal to 0: self-distances would be infinite.
- Ignoring parallel edges: only the smallest weight between a pair matters.
- Pruning with
if d[i][k] == INFincorrectly: it is a valid and important optimisation.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.