Network Delay Time

1. The obvious way

   Bellman-Ford relaxes every edge n times: O(n x edges), correct but slower.

2. The key insight

   Build lists of (neighbour, delay) per node. Heap holds (arrival time, node), starting with (0, k). Pop the smallest; if the node was already settled skip it; else record its arrival time and push each unsettled neighbour with time + delay. If all n nodes got a time, the answer is the largest of them; otherwise -1.

3. The algorithm
   1. Build neighbours with delays; heap = [(0, k)].
   2. Pop the earliest arrival; skip if already settled.
   3. Record its time; push neighbours with time + delay.
   4. All nodes settled: return the largest time; else -1.

Watch it run

heard: 2 at 0

import heapq

def network_delay_time(times, n, k):
    lanes = {node: [] for node in range(1, n + 1)}
    for start, end, minutes in times:
        lanes[start].append((end, minutes))
    arrivals = [(0, k)]                                # min-heap of (arrival time, person)
    heard_at = {}
    while arrivals:
        time, person = heapq.heappop(arrivals)
        if person in heard_at:
            continue                                   # already told earlier
        heard_at[person] = time
        for friend, minutes in lanes[person]:
            if friend not in heard_at:
                heapq.heappush(arrivals, (time + minutes, friend))
    return max(heard_at.values()) if len(heard_at) == n else -1

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.