Graphs crash course ↗ · 104

743. Network Delay Time

Find the minimum time for a signal to reach all nodes in a directed, weighted graph. Run Dijkstra's algorithm from the source with a min-heap; the answer is the largest finalized distance, or -1 if any node stays unreachable.

● MediumDijkstraShortest PathMin-HeapTypeScript

PROBLEM What we're solving

You have n network nodes (labeled 1 to n) and directed, weighted edges in times[i] = [u, v, w] (signal travels from u to v in w time units). A signal starts at node k. Return the minimum time for all nodes to receive the signal, or -1 if any node is unreachable.

Worked example. times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2. Starting from node 2: node 1 costs 1, node 3 costs 1, node 4 costs 2. The last node to receive the signal is node 4 at time 2. Answer: 2.

KEY IDEA Dijkstra: greedily finalize the nearest unvisited node

Insight → since all edge weights are non-negative, the node currently nearest to the source will never get a shorter path via any future detour. Greedily finalize it, then relax its outgoing edges. A min-heap of (distance, node) pairs delivers the nearest unfinalized node in O(log n). The answer is max(dist.values()) — the last node that the signal reaches — or -1 if fewer than n nodes were finalized.

RECIPE Dijkstra from source, max of distances

0 · Build adjacency list. Collect (dst, weight) neighbors for every source node. This makes edge lookups O(degree).
1 · Seed the min-heap. Push (0, k) — distance zero at the starting node. Keep a dist map (node → finalized distance).
2 · Pop the minimum. Extract the (d, u) pair with the smallest d. If u is already finalized, skip it — a stale entry from a prior relaxation.
3 · Finalize u. Record dist[u] = d. This distance is optimal and will never decrease.
4 · Relax neighbors. For each unfinalized neighbor v, push (d + weight, v) onto the heap.
5 · Repeat until heap is empty. All reachable nodes are finalized.
6 · Answer. If dist.size < n, return -1 (some node unreachable). Otherwise return Math.max(...dist.values()).

Classic confusion → the heap can contain stale entries for the same node. Never update an existing heap entry in place — just push a new one and skip the duplicate when you pop it (if (dist.has(u)) continue). Beginners sometimes use a separate "visited set" outside the heap check, or forget to skip duplicates, leading to incorrect double-relaxations.

COST Complexity & alternatives

Bellman-Ford

O(V · E)

Works with negative weights, but slow for dense graphs.

Dijkstra + min-heap

O((V + E) log V)

O(V + E) space. Optimal for non-negative weights.

Space note

The adjacency list is O(V + E). The heap holds at most O(E) entries (one per relaxation). The dist map is O(V). A Fibonacci heap could achieve O(V log V + E) but is rarely used in practice.

Pattern transfer → Dijkstra is the template for Cheapest Flights Within K Stops (modified Dijkstra with a hop-count dimension), Path With Minimum Effort (minimize the max edge along a path), Swim in Rising Water (binary-search on time or minimax Dijkstra), and any "shortest path in a weighted directed graph" question with non-negative weights.

RUN IT Dijkstra from source - pop nearest, relax neighbors

edges (u,v,w|...) =n =k =

step 0 / 10

STARTSource node 2, 4 nodes total. Heap seeded with (0, 2). All distances start at ∞.dist map is empty; finalized nodes will be added to it.

1function networkDelayTime(times: number[][], n: number, k: number): number {
2  // Build adjacency list: src -> [(dst, weight)]
3▶  const adj = new Map<number, [number, number][]>();
4▶  for (let i = 1; i <= n; i++) adj.set(i, []);
5▶  for (const [u, v, w] of times) {
6▶    adj.get(u)!.push([v, w]);
7  }
8 
9  // Min-heap ordered by (dist, node). Encode as [dist, node].
10▶  const dist = new Map<number, number>();
11  // Simple min-heap via sorted array (replace with binary heap for production)
12▶  const heap: [number, number][] = [[0, k]];
13 
14  while (heap.length > 0) {
15    heap.sort((a, b) => a[0] - b[0]);
16    const [d, u] = heap.shift()!;
17    if (dist.has(u)) continue;   // already finalized
18    dist.set(u, d);
19    for (const [v, w] of (adj.get(u) ?? [])) {
20      if (!dist.has(v)) {
21        heap.push([d + w, v]);
22      }
23    }
24  }
25 
26  if (dist.size !== n) return -1;
27  return Math.max(...dist.values());
28}

dist[node]∞1∞2∞3∞4

State

{}

dist{}

(0,2)

heap

k (src)

current / heap entryfinalized node / dist mapanswer / finalized diststale / unreachable

slowfast

TYPESCRIPT The solution, annotated

networkDelayTime.ts
function networkDelayTime(times: number[][], n: number, k: number): number {
  // Build adjacency list: src -> [(dst, weight)]
  const adj = new Map<number, [number, number][]>();
  for (let i = 1; i <= n; i++) adj.set(i, []);
  for (const [u, v, w] of times) {
    adj.get(u)!.push([v, w]);
  }

  // Min-heap ordered by (dist, node). Encode as [dist, node].
  const dist = new Map<number, number>();
  // Simple min-heap via sorted array (replace with binary heap for production)
  const heap: [number, number][] = [[0, k]];

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, u] = heap.shift()!;
    if (dist.has(u)) continue;   // already finalized
    dist.set(u, d);
    for (const [v, w] of (adj.get(u) ?? [])) {
      if (!dist.has(v)) {
        heap.push([d + w, v]);
      }
    }
  }

  if (dist.size !== n) return -1;
  return Math.max(...dist.values());
}

Reading it block by block

Lines 2–6 — build the adjacency list. We initialize an empty neighbor list for every node 1..n, then populate it from times. Using a Map keeps lookup clean and avoids off-by-one index bugs with the 1-based node labels.

Lines 9–10 — initialize the heap and dist map. The heap starts with [0, k] — cost zero to reach the source from itself. The distmap will hold finalized shortest distances; it doubles as the "visited" check.

Lines 12–13 — pop minimum, skip stale. We sort and shift to get the cheapest entry. If dist.has(u) is already true, this is a stale heap entry from an earlier relaxation — skip it. This is the critical correctness guard.

Lines 14–18 — finalize and relax. We record dist[u] = d (now optimal). For each unfinalized neighbor v, we push [d + w, v] onto the heap. We only skip already-finalized neighbors to avoid wasted heap entries.

Lines 22–23 — final answer. If fewer than n nodes were finalized, some node is unreachable — return -1. Otherwise the answer is Math.max(...dist.values()): the time the last node receives the signal.

Complexity → O((V + E) log V) time with a binary min-heap — each edge triggers at most one push (O(log V)) and each node is finalized once (O(log V) for the pop). O(V + E) space for the adjacency list, dist map, and heap.

INTERVIEWFollow-ups they'll ask

"What if edge weights can be negative?" Dijkstra breaks. Switch to Bellman-Ford (O(VE)) or SPFA. Negative cycles make the problem undefined.
"What if there's a hop count limit?" See Cheapest Flights Within K Stops: add a hop dimension to the state (cost, node, hopsLeft) and use a modified Dijkstra or Bellman-Ford over K iterations.
"Return the actual path, not just the time?" Track a parent map: on each finalization record parent[u] = prevNode, then trace back from the last-reached node.
"What if the graph has undirected edges?" Add both directions in the adjacency list. Everything else stays the same.
"Edge case: k has no outgoing edges?" Only node k is finalized; dist.size === 1, which is less than n (for n > 1) → return -1.

OPTIMAL Dijkstra

networkDelayTime.ts
function networkDelayTime(times: number[][], n: number, k: number): number {
  // Build adjacency list: src -> [(dst, weight)]
  const adj = new Map<number, [number, number][]>();
  for (let i = 1; i <= n; i++) adj.set(i, []);
  for (const [u, v, w] of times) {
    adj.get(u)!.push([v, w]);
  }

  // Min-heap ordered by (dist, node). Encode as [dist, node].
  const dist = new Map<number, number>();
  // Simple min-heap via sorted array (replace with binary heap for production)
  const heap: [number, number][] = [[0, k]];

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, u] = heap.shift()!;
    if (dist.has(u)) continue;   // already finalized
    dist.set(u, d);
    for (const [v, w] of (adj.get(u) ?? [])) {
      if (!dist.has(v)) {
        heap.push([d + w, v]);
      }
    }
  }

  if (dist.size !== n) return -1;
  return Math.max(...dist.values());
}

ALT 1 Brute force — Bellman-Ford relaxation

O(n · E) time · O(n) space

Skip the priority queue entirely: initialise every distance to Infinity, then relax all edges n − 1 times. Simpler to reason about than Dijkstra — just repeatedly apply the rule dist[v] = min(dist[v], dist[u] + w).

approach-2.ts
function networkDelayTime(times: number[][], n: number, k: number): number {
  const dist = new Array<number>(n + 1).fill(Infinity);
  dist[k] = 0;

  // Relax every edge n-1 times; shortest paths use at most n-1 edges.
  for (let iter = 0; iter < n - 1; iter++) {
    let changed = false;
    for (const [u, v, w] of times) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }
    if (!changed) break; // early exit once nothing improves
  }

  let ans = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1; // some node unreachable
    ans = Math.max(ans, dist[i]);
  }
  return ans;
}

Note → Correct for non-negative weights and dead simple, but it touches every edge up to n − 1times — O(n · E) — versus Dijkstra's O(E log n). On dense graphs the extra passes add up. Dijkstra finalises each node once by always expanding the closest unsettled vertex via a min-heap.

MNEMONIC The one-liner

"Pop the nearest, skip the stale, relax the fresh — the last signal arrival is the answer."

TRIGGERS When you see _ → reach for _

shortest path, non-negative weights	Dijkstra + min-heap
"minimum time / cost to reach all nodes"	Dijkstra, return max(dist)
weighted directed graph, single source	dist map + heap seeded at (0, src)
"return -1 if unreachable"	check dist.size === n after loop

SKELETON The reusable shape

skeleton.ts
const adj = new Map<number, [number, number][]>();
for (const [u, v, w] of times) adj.get(u)!.push([v, w]);

const dist = new Map<number, number>();
const heap: [number, number][] = [[0, k]];  // [dist, node]

while (heap.length) {
  heap.sort((a, b) => a[0] - b[0]);
  const [d, u] = heap.shift()!;
  if (dist.has(u)) continue;
  dist.set(u, d);
  for (const [v, w] of adj.get(u) ?? []) {
    if (!dist.has(v)) heap.push([d + w, v]);
  }
}
return dist.size !== n ? -1 : Math.max(...dist.values());

FLASHCARDS Tap to flip

Why does Dijkstra require non-negative edge weights?

With negative weights, a later path could undercut a finalized distance, violating the greedy invariant.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Given times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2, what does the algorithm return?

QUESTION 02

Why do we skip a popped node if it already appears in the dist map?

QUESTION 03

What is the time complexity of Dijkstra with a binary min-heap?

QUESTION 04

A graph has 4 nodes but Dijkstra only finalizes 3. What should you return?

QUESTION 05

The heap is seeded with [0, k]. What does each entry [d, u] represent?

QUESTION 06

Which change would make Dijkstra give incorrect results?

QUESTION 07

After Dijkstra finishes, how do you compute the network delay time?

QUESTION 08

#743 · Network Delay TimeDijkstra's algorithm from the source with a min-heap of (dist, node). The answer is the maximum finalized distance across all nodes; return −1 if any node is unreachable.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Dijkstra: greedily finalize the nearest unvisited node

RECIPE Dijkstra from source, max of distances

COST Complexity & alternatives

Space note

RUN IT Dijkstra from source - pop nearest, relax neighbors

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Dijkstra

ALT 1 Brute force — Bellman-Ford relaxation

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _