NeetCode #628LC-743MediumAdvanced GraphsNC 150NC 250
← Back to All Problems#628 · #743 · Network Delay Time(网络延迟时间)
📌 Problem Statement & Constraints
You are given
times where times[i] = [u, v, w] is a directed edge taking w time, and n nodes labelled 1..n. Starting from node k, return the time for all nodes to receive the signal, or -1 if impossible. Constraints: 1 <= k <= n <= 100, 1 <= times.length <= 6000, 0 <= w <= 100.💡 Core Algorithmic Approaches
- This is the single-source shortest path problem, so Dijkstra applies (all weights are non-negative).
- Use a min-heap of
(distance, node); settle each node once. - The answer is the maximum settled distance, provided all
nnodes are reached. - The lazy-deletion pattern (skip nodes already settled) keeps the heap simple.
💻 Benchmark Python3 Implementation
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
import heapq
from collections import defaultdict
g = defaultdict(list)
for u, v, w in times:
g[u].append((v, w))
dist = {}
h = [(0, k)]
while h:
d, node = heapq.heappop(h)
if node in dist:
continue # already settled with a smaller distance
dist[node] = d
for nxt, w in g[node]:
if nxt not in dist:
heapq.heappush(h, (d + w, nxt))
return max(dist.values()) if len(dist) == n else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(E log V): each edge is relaxed once.
💾 Space Complexity
O(V + E) for the graph and the distance map.
⚠️ Interview Pitfalls & Follow-ups
- Using BFS: the weights differ, so a plain queue does not give shortest paths.
- Marking settled when pushing: a shorter path could arrive later and be ignored.
- Forgetting the unreachable check: some nodes may never receive the signal.
- Using Bellman-Ford: correct but slower; Dijkstra is the right tool for non-negative weights.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.