743 - Network Delay Time

Difficulty: Medium | Pattern: Dijkstra's Shortest Path | Company tags: Amazon, Google, Facebook

Problem Statement

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Approach: Dijkstra — O((V+E) log V)

import heapq
from collections import defaultdict

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((w, v))
    
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for w, v in graph[u]:
            new_dist = d + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    
    max_dist = max(dist.values())
    return max_dist if max_dist < float('inf') else -1

Dry Run

times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2

Graph: 2→1(1), 2→3(1), 3→4(1)

Step	heap	dist
Start	[(0,2)]	1:inf, 2:0, 3:inf, 4:inf
Pop (0,2)	[(1,1),(1,3)]	1:1, 2:0, 3:1, 4:inf
Pop (1,1)	[(1,3)]	no change for 1's neighbors
Pop (1,3)	[(2,4)]	4:2
Pop (2,4)	[]	done

max(1,0,1,2) = 2 ✓

Edge Cases

• Disconnected node → dist stays infinity → return -1
• Single node → return 0

Complexity

• Time: O((V + E) log V)
• Space: O(V + E)