MediumNeetCode150Depth-First SearchBreadth-First SearchGraphHeap (Priority Queue)Shortest Path
Network Delay Time
Time for all nodes to receive signal.
Examples
Input
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output
2
Signal: 2->1 (1), 2->3 (1), 3->4 (1). Max delay: 2.
Constraints
- •
1 <= k <= n <= 100 - •
1 <= times.length <= 6000
Approaches
BFS from k.
CodeT: O(V+E) | S: O(V+E) queue
Shortest path from k.
CodeT: O(E log E) | S: O(V+E)
import heapq
def networkDelayTime(times, n, k):
g={i:[] for i in range(1,n+1)}
for u,v,w in times: g[u].append((v,w))
h=[(0,k)]; dist={}
while h:
d,u=heapq.heappop(h)
if u in dist: continue
dist[u]=d
for v,w in g[u]:
if v not in dist: heapq.heappush(h,(d+w,v))
return max(dist.values()) if len(dist)==n else -1Same approach.
CodeT: O(E log V) | S: O(V+E)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| BFS | O(V+E) | O(V+E) queue | BFS from k. |
| Dijkstra | O(E log E) | O(V+E) | Shortest path from k. |
| Dijkstra Optimized | O(E log V) | O(V+E) | Same approach. |
BFS
T: O(V+E)S: O(V+E) queue
BFS from k.
Dijkstra
T: O(E log E)S: O(V+E)
Shortest path from k.
Dijkstra Optimized
T: O(E log V)S: O(V+E)
Same approach.
Common Mistakes
Not handling unreachable nodes
Using wrong priority queue
Not tracking visited