LeetCode 743 · Medium · Advanced Graphs

Network Delay Time

A signal leaves node k and travels along directed, timed edges times[i] = (u, v, w). Return how long until all n nodes have heard it, or -1 if some node never does.

O(E log E)time
O(V + E)space
Dijkstramin-heap of arrival times

edges separated by ";" · up to 14 · nodes 1..n · n: 1–8 · w: 0 to 20 · no repeated (u, v) pair, no self-loops

minHeap · (time, node), smallest first

public int networkDelayTime(int[][] times, int n, int k) { Map<Integer, List<int[]>> edges = new HashMap<>(); for (int[] e : times) { edges.putIfAbsent(e[0], new ArrayList<>()); edges.get(e[0]).add(new int[]{e[1], e[2]}); } PriorityQueue<int[]> minHeap = new PriorityQueue<>( (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); minHeap.offer(new int[]{0, k}); // {time, node} Set<Integer> visit = new HashSet<>(); int t = 0; while (!minHeap.isEmpty()) { int[] top = minHeap.poll(); int w1 = top[0]; int n1 = top[1]; if (visit.contains(n1)) { continue; // stale, a faster path won } visit.add(n1); t = w1; for (int[] edge : edges.getOrDefault(n1, List.of())) { int n2 = edge[0]; int w2 = edge[1]; if (!visit.contains(n2)) { minHeap.offer(new int[]{w1 + w2, n2}); } } } return visit.size() == n ? t : -1;}
(w1, n1)
—
t
0
visit
{}
heap size
1

Why it works

  1. Brute force relaxes every edge n − 1 times (Bellman-Ford): O(V · E). It also handles negative weights, which this problem never has.
  2. The heap pops nodes in order of arrival time. With no negative edges, the smallest time in the heap can't be beaten by any detour through slower nodes, so the first pop of a node is final. That is Dijkstra's invariant.
  3. Each edge pushes at most once: E pushes and pops, O(log E) each, so O(E log E) time and O(V + E) space for the adjacency list and heap.
  4. Pitfall: a node can sit in the heap several times, pushed by different paths. Skip the later, slower copies with the visit check, or they would overwrite t.
  5. The answer is the last pop, because pops come in increasing time order: t ends as the largest shortest-path time. If some node never pops, visit.size() < n and the answer is -1. Related: Path With Minimum Effort (1631), Cheapest Flights (787).