Network Delay Time (LeetCode 743)

The problem

There are n nodes labelled 1 to n. Each entry [u, v, w] in times is a directed edge: a signal sent from u reaches v after w time units. A signal starts at node k. Return how long it takes until every node has received it. If some node can never receive it, return -1.

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

From node 2, the signal reaches 1 and 3 after 1 unit, and 4 after 2 units (via 3). The last node hears it at time 2.

How to think about it

Start with brute force. Every node receives the signal along its shortest path from k, so the answer is the largest of those shortest distances. You could try every simple path from k to each node and keep the cheapest, but the number of paths grows exponentially. Plain BFS doesn’t work either: BFS finds fewest edges, and here edges have different weights.

The key insight: always finalise the closest unfinished node next. This is Dijkstra’s algorithm. Keep a min-heap of (distance, node) candidates, starting with (0, k). Pop the smallest. Because all weights are non-negative, no later path can reach that node more cheaply, since any other route would go through a node that’s already at least as far. So its distance is final. Then push (d + w, v) for each outgoing edge to a node not yet finalised.

Lazy deletion keeps the code short. A node may be pushed several times with different distances. You don’t update entries in the heap; you just skip a popped entry if the node is already in dist. The first pop of a node is always its shortest distance.

Which pattern is this? Single-source shortest path with non-negative weights: Dijkstra. The tell is “weighted graph, minimum total cost or time from one source”. The final answer is max(dist.values()), or -1 if fewer than n nodes were reached.

Approach

1. Build an adjacency list u → [(v, w)].
2. Start a heap with (0, k) and an empty dist dict.
3. Pop (d, u). If u is already in dist, skip. Otherwise set dist[u] = d.
4. For each edge (v, w) out of u with v not finalised, push (d + w, v).
5. When the heap is empty, return max(dist.values()) if all n nodes are in dist, else -1.

Solution

import heapq
from collections import defaultdict
def network_delay_time(times, n, k):
    adj = defaultdict(list)
    for u, v, w in times: adj[u].append((v, w))
    dist = {}; h = [(0, k)]
    while h:
        d, u = heapq.heappop(h)                   # closest candidate so far
        if u in dist: continue                    # stale entry: already finalised
        dist[u] = d                               # first pop is the shortest distance
        for v, w in adj[u]:
            if v not in dist: heapq.heappush(h, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1   # last node to hear the signal
# network_delay_time([[2,1,1],[2,3,1],[3,4,1]], 4, 2) -> 2

Dry run

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

All four nodes are reached and the largest distance is 2. To see a stale entry: with [[1,2,4],[1,3,1],[3,2,1]], n = 3, k = 1, node 2 is pushed as (4, 2) and later as (2, 2). The (2, 2) pops first and wins; (4, 2) is skipped. The answer is 2.

Complexity

• Time: O(E log E), which is O(E log V). Each edge can push one heap entry, and each push or pop costs O(log E). Since E ≤ V², log E ≤ 2 log V.
• Space: O(V + E) for the adjacency list, the heap and dist.

Edge cases and pitfalls

• Unreachable node returns -1: in [[1,2,1]] with k = 2, node 1 is never reached.
• A single node with no edges returns 0.
• Using BFS gives fewest hops, not least time. With weights, you need Dijkstra.
• Forgetting the stale-entry check makes later, larger distances overwrite the correct ones.
• Negative weights break Dijkstra. This problem guarantees non-negative times; otherwise use Bellman-Ford.

Related problems

• Cheapest Flights Within K Stops (LeetCode 787): shortest path with a limit on edges, where Bellman-Ford is the cleaner fit.
• Path With Minimum Effort (LeetCode 1631): Dijkstra on a grid, where a path’s cost is its largest step.
• Path with Maximum Probability (LeetCode 1514): Dijkstra with a max-heap, multiplying probabilities instead of adding.