⚡Flashcard Drill➔
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

  1. All-pairs shortest paths are needed, and n <= 100 makes Floyd-Warshall ideal.
  2. After the O(n^3) DP, each row gives the distances from one city.
  3. Count the entries at most distanceThreshold, and pick the minimum count with the largest index on ties.
  4. 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] == INF incorrectly: 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems