Network Delay Time (LeetCode 743)
A network has n nodes, labeled 1 through n, connected by directed wires times[i] = (ui, vi, wi): a signal takes wi time units to travel from ui to vi.
A signal is broadcast from a single node k. Return the time it takes for the last node to receive it -- the smallest t such that every one of the n nodes has heard the signal by time t. Return -1 if some node never receives it.
Worked Examples
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 222 the signal reaches nodes 1 and 3 at time 1, then node 4 at time 2.times = [[1,2,1]], n = 2, k = 112 hears the signal at time 1.times = [[1,2,1]], n = 2, k = 2-11 to 2, so a signal starting at 2 never reaches 1.⚖️Formal Constraints & Bounds
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100All the pairs
(ui, vi)are unique. (i.e., no multiple edges.)
Core Insight
Dijkstra finalizes node distances in monotonically increasing order. With non-negative edge weights, the first time a node is popped from the min-heap represents its globally optimal shortest path.
Real-World Scenario & Production Applications
GPS navigation routing (Google Maps/OSRM finding lowest-latency traffic routes) and packet routing in telecommunication networks (OSPF).
Subproblems & Recurrence Decomposition3 Phases
Initialize distance map dist = {k: 0} and min-heap [(0, k)]. All other vertices start with infinite distance.
min_heap = [(0, k)] # (distance, node)
dist = {k: 0}Step-by-Step Execution Trace Table
| Step | Popped Element (dist, node) | Action | Finalized dist Table | Heap State After Relaxation |
|---|---|---|---|---|
| 0 | — | Seed source node k = 1 | {} | [(0, 1)] |
| 1 | (0, 1) | Finalize node 1 at dist 0. Relax neighbors 2 (w=1) and 3 (w=7). | {1: 0} | [(1, 2), (7, 3)] |
| 2 | (1, 2) | Finalize node 2 at dist 1. Relax neighbor 3 (w=2 dist 3). | {1: 0, 2: 1} | [(3, 3), (7, 3)] |
| 3 | (3, 3) | Finalize node 3 at dist 3. Relax neighbor 4 (w=1 dist 4). | {1: 0, 2: 1, 3: 3} | [(4, 4), (7, 3)] |
| 4 | (4, 4) | Finalize node 4 at dist 4. | {1: 0, 2: 1, 3: 3, 4: 4} | [(7, 3)] |
| 5 | (7, 3) | Node 3 already in dist stale entry pruned! | {1: 0, 2: 1, 3: 3, 4: 4} | [] |
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 22| Step | Popped Element (dist, node) | Action | Finalized dist Table | Heap State After Relaxation |
|---|---|---|---|---|
| 0 | — | Seed source node k = 1 | {} | [(0, 1)] |
| 1 | (0, 1) | Finalize node 1 at dist 0. Relax neighbors 2 (w=1) and 3 (w=7). | {1: 0} | [(1, 2), (7, 3)] |
| 2 | (1, 2) | Finalize node 2 at dist 1. Relax neighbor 3 (w=2 dist 3). | {1: 0, 2: 1} | [(3, 3), (7, 3)] |
| 3 | (3, 3) | Finalize node 3 at dist 3. Relax neighbor 4 (w=1 dist 4). | {1: 0, 2: 1, 3: 3} | [(4, 4), (7, 3)] |
| 4 | (4, 4) | Finalize node 4 at dist 4. | {1: 0, 2: 1, 3: 3, 4: 4} | [(7, 3)] |
| 5 | (7, 3) | Node 3 already in dist stale entry pruned! | {1: 0, 2: 1, 3: 3, 4: 4} | [] |
| 1 | adj = [[] for _ in range(n + 1)] |
| 2 | adj[u].append((v, w)) for every edge |
| 3 | dist = {every node: inf}; dist[k] = 0 |
| 4 | pq = [(0, k)] |
| 5 | while pq: |
| 6 | d, u = heappop(pq) |
| 7 | if d > dist[u]: |
| 8 | continue |
| 9 | for v, weight in adj[u]: |
| 10 | if dist[u] + weight < dist[v]: |
| 11 | dist[v] = dist[u] + weight |
| 12 | heappush(pq, (dist[v], v)) |
| 13 | answer = max(dist.values()) |
| 14 | return answer if answer < inf else -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a directed graph with non-negative edge weights. A priority queue greedily extracts the unvisited vertex with the smallest provisional distance. Relaxing outgoing edges guarantees that when a node is popped from the min-heap, its minimal distance is finalized. The overall delay time is the maximum of the shortest distances to all reachable nodes.
🚦 The Analogy: A Toll Road Network Where You Always Take the Cheapest Ticket Next
Imagine you're tracking the cheapest known cost to reach every city from your starting point, and you keep a stack of "tickets" for cities you haven't finalized yet, sorted cheapest-first. You always process the cheapest ticket on top of the stack next. Once you finalize a city's cost, you never need to revisit it — because every other route to it would have to pass through a city that's at least as expensive as the one you just finalized (since no road costs a negative toll), which can only make the total more expensive, never less.
🔑 The Key Idea in the Code
The if d > dist[u]: continue guard handles the case where a node got pushed onto the heap multiple times at different candidate distances — only the pop whose cost still equals dist[u] is trusted; every later, more expensive entry for that same node is simply discarded.
Missing Dijkstra stale heap entry skip: In lazy Dijkstra, nodes pushed with earlier, worse distances remain in the heap. Without
if d > dist[u]: continue, every stale copy ofuscansadj[u]again: the answer stays right, but the edge scans are no longer E in total, and dense graphs slow down badly.1-based node indexing off-by-one: Vertices are labeled from
1ton. Allocatingdistarray of sizeninstead ofn + 1causesIndexError: list index out of range.Unreachable node output error: Returning
max(dist.values())without checking if any node was never reached. Iflen(dist) < n(or anydist[i] == float('inf')), the signal cannot reach all nodes; you must return-1.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The wires are directed, "a signal takes wi time units to travel from ui to vi" with 0 <= wi, and the answer is the moment "every one of the n nodes has heard the signal": each node hears it along its cheapest path from k, and the answer is the largest of those times. Cheapest paths from one source with non-negative weights is Dijkstra.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Whenever (d, u) is popped with d == dist[u], dist[u] is final: no path to u is shorter. A popped entry with d > dist[u] is stale and skipped; otherwise each edge u -> v is relaxed with dist[u] + weight < dist[v], and only an improved dist[v] is pushed.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Every node hears the signal along its cheapest path from k, and the weights are never negative, so I'd use Dijkstra. I keep dist, the best known time per node, and a min-heap of time and node pairs, starting with zero at k. I always pop the smallest time. With non-negative weights, any other way to reach that node has to leave the settled area through a node that is at least as far, so the popped time is final. Then I relax each outgoing edge, and push a neighbour only when its time improves. The trap is the stale entry: a node can be in the heap several times, so when the popped time is bigger than dist of u, I skip it; otherwise old copies rescan their edges. The answer is the largest dist, or minus one if some node is still unreached. It's O((V plus E) log V) time and O(V plus E) space."
Complexity & Mathematical Proof
O((V + E) log V)
Look at the code: building adj reads the E edges once and dist gets V entries, O(V + E). A pop that is not stale has d == dist[u], and with non-negative weights dist[u] never drops after that, so each node scans adj[u] at most once: E edge checks in total. Each check pushes at most once (only when dist[v] improves), so pq sees at most E + 1 pushes and E + 1 pops. A heap operation on at most E + 1 entries costs O(log E), and log E <= 2 log V because E <= V^2. Total: O(V + E) setup plus O(E log V) heap work, written O((V + E) log V).
O(V + E)
adj holds V + 1 lists with E entries, dist holds V entries, and pq holds at most E + 1 entries at once, since each push comes from one edge check. There is no recursion. The answer is one integer.
T(V, E) = (V + E) setup + E edge checks + (E + 1) pushes and pops * O(log V) = O((V + E) log V)
Derivation Progression
adj = [[] for _ in range(n + 1)], dist over 1..n: O(V); for u, v, w in times: O(E)
Every edge is stored once in its source's list.
if d > dist[u]: continue skips every pop but the one with d == dist[u]: E edge checks in total
With non-negative weights dist[u] is final once popped, so adj[u] is scanned once.
at most E + 1 heappush and E + 1 heappop, O(log E) = O(log V) each
A push happens only when dist[v] improves, at most once per edge check; log E <= 2 log V.
max(dist.values()): O(V)
The largest settled time, or -1 if some node is still infinite.
Variable Definitions
Number of nodes, n
Number of directed edges, len(times)
Memory Architecture & Bounds
O(1): no recursion
O(V + E): adj (E entries), dist (V entries) and pq (at most E + 1 entries)
O(1): one integer
Boundary Best / Worst Cases
when the source has no outgoing edge: dist and adj are still built, and pq pops once.
.
when many edges improve a dist and push, so pq grows toward E entries.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: Bellman-Ford's relaxations are fine here (), but road and computer networks with millions of nodes need Dijkstra's .
nodes, at most 6000 edges, weights : every edge is checked once, so pq never holds more than entries.
A negative weight (a refund, a credit) silently breaks the settled-means-final rule, so check the input at the boundary. When only one target matters, as in route planning, stop as soon as the target is popped instead of settling every node.
Core Algorithmic State Invariants
- Example 1, Settled in Order
From k = 2: node 2 pops at time 0, nodes 1 and 3 at time 1, node 4 at time 2. Every node is reached, so the answer is the largest time, 2.
Network Delay Time (LeetCode 743)
A network has n nodes, labeled 1 through n, connected by directed wires times[i] = (ui, vi, wi): a signal takes wi time units to travel from ui to vi.
A signal is broadcast from a single node k. Return the time it takes for the last node to receive it -- the smallest t such that every one of the n nodes has heard the signal by time t. Return -1 if some node never receives it.
Worked Examples
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 222 the signal reaches nodes 1 and 3 at time 1, then node 4 at time 2.times = [[1,2,1]], n = 2, k = 112 hears the signal at time 1.times = [[1,2,1]], n = 2, k = 2-11 to 2, so a signal starting at 2 never reaches 1.⚖️Formal Constraints & Bounds
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100All the pairs
(ui, vi)are unique. (i.e., no multiple edges.)
Core Insight
Dijkstra finalizes node distances in monotonically increasing order. With non-negative edge weights, the first time a node is popped from the min-heap represents its globally optimal shortest path.
Real-World Scenario & Production Applications
GPS navigation routing (Google Maps/OSRM finding lowest-latency traffic routes) and packet routing in telecommunication networks (OSPF).
Subproblems & Recurrence Decomposition3 Phases
Initialize distance map dist = {k: 0} and min-heap [(0, k)]. All other vertices start with infinite distance.
min_heap = [(0, k)] # (distance, node)
dist = {k: 0}Step-by-Step Execution Trace Table
| Step | Popped Element (dist, node) | Action | Finalized dist Table | Heap State After Relaxation |
|---|---|---|---|---|
| 0 | — | Seed source node k = 1 | {} | [(0, 1)] |
| 1 | (0, 1) | Finalize node 1 at dist 0. Relax neighbors 2 (w=1) and 3 (w=7). | {1: 0} | [(1, 2), (7, 3)] |
| 2 | (1, 2) | Finalize node 2 at dist 1. Relax neighbor 3 (w=2 dist 3). | {1: 0, 2: 1} | [(3, 3), (7, 3)] |
| 3 | (3, 3) | Finalize node 3 at dist 3. Relax neighbor 4 (w=1 dist 4). | {1: 0, 2: 1, 3: 3} | [(4, 4), (7, 3)] |
| 4 | (4, 4) | Finalize node 4 at dist 4. | {1: 0, 2: 1, 3: 3, 4: 4} | [(7, 3)] |
| 5 | (7, 3) | Node 3 already in dist stale entry pruned! | {1: 0, 2: 1, 3: 3, 4: 4} | [] |
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 22| Step | Popped Element (dist, node) | Action | Finalized dist Table | Heap State After Relaxation |
|---|---|---|---|---|
| 0 | — | Seed source node k = 1 | {} | [(0, 1)] |
| 1 | (0, 1) | Finalize node 1 at dist 0. Relax neighbors 2 (w=1) and 3 (w=7). | {1: 0} | [(1, 2), (7, 3)] |
| 2 | (1, 2) | Finalize node 2 at dist 1. Relax neighbor 3 (w=2 dist 3). | {1: 0, 2: 1} | [(3, 3), (7, 3)] |
| 3 | (3, 3) | Finalize node 3 at dist 3. Relax neighbor 4 (w=1 dist 4). | {1: 0, 2: 1, 3: 3} | [(4, 4), (7, 3)] |
| 4 | (4, 4) | Finalize node 4 at dist 4. | {1: 0, 2: 1, 3: 3, 4: 4} | [(7, 3)] |
| 5 | (7, 3) | Node 3 already in dist stale entry pruned! | {1: 0, 2: 1, 3: 3, 4: 4} | [] |
| 1 | adj = [[] for _ in range(n + 1)] |
| 2 | adj[u].append((v, w)) for every edge |
| 3 | dist = {every node: inf}; dist[k] = 0 |
| 4 | pq = [(0, k)] |
| 5 | while pq: |
| 6 | d, u = heappop(pq) |
| 7 | if d > dist[u]: |
| 8 | continue |
| 9 | for v, weight in adj[u]: |
| 10 | if dist[u] + weight < dist[v]: |
| 11 | dist[v] = dist[u] + weight |
| 12 | heappush(pq, (dist[v], v)) |
| 13 | answer = max(dist.values()) |
| 14 | return answer if answer < inf else -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a directed graph with non-negative edge weights. A priority queue greedily extracts the unvisited vertex with the smallest provisional distance. Relaxing outgoing edges guarantees that when a node is popped from the min-heap, its minimal distance is finalized. The overall delay time is the maximum of the shortest distances to all reachable nodes.
🚦 The Analogy: A Toll Road Network Where You Always Take the Cheapest Ticket Next
Imagine you're tracking the cheapest known cost to reach every city from your starting point, and you keep a stack of "tickets" for cities you haven't finalized yet, sorted cheapest-first. You always process the cheapest ticket on top of the stack next. Once you finalize a city's cost, you never need to revisit it — because every other route to it would have to pass through a city that's at least as expensive as the one you just finalized (since no road costs a negative toll), which can only make the total more expensive, never less.
🔑 The Key Idea in the Code
The if d > dist[u]: continue guard handles the case where a node got pushed onto the heap multiple times at different candidate distances — only the pop whose cost still equals dist[u] is trusted; every later, more expensive entry for that same node is simply discarded.
Missing Dijkstra stale heap entry skip: In lazy Dijkstra, nodes pushed with earlier, worse distances remain in the heap. Without
if d > dist[u]: continue, every stale copy ofuscansadj[u]again: the answer stays right, but the edge scans are no longer E in total, and dense graphs slow down badly.1-based node indexing off-by-one: Vertices are labeled from
1ton. Allocatingdistarray of sizeninstead ofn + 1causesIndexError: list index out of range.Unreachable node output error: Returning
max(dist.values())without checking if any node was never reached. Iflen(dist) < n(or anydist[i] == float('inf')), the signal cannot reach all nodes; you must return-1.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The wires are directed, "a signal takes wi time units to travel from ui to vi" with 0 <= wi, and the answer is the moment "every one of the n nodes has heard the signal": each node hears it along its cheapest path from k, and the answer is the largest of those times. Cheapest paths from one source with non-negative weights is Dijkstra.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Whenever (d, u) is popped with d == dist[u], dist[u] is final: no path to u is shorter. A popped entry with d > dist[u] is stale and skipped; otherwise each edge u -> v is relaxed with dist[u] + weight < dist[v], and only an improved dist[v] is pushed.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Every node hears the signal along its cheapest path from k, and the weights are never negative, so I'd use Dijkstra. I keep dist, the best known time per node, and a min-heap of time and node pairs, starting with zero at k. I always pop the smallest time. With non-negative weights, any other way to reach that node has to leave the settled area through a node that is at least as far, so the popped time is final. Then I relax each outgoing edge, and push a neighbour only when its time improves. The trap is the stale entry: a node can be in the heap several times, so when the popped time is bigger than dist of u, I skip it; otherwise old copies rescan their edges. The answer is the largest dist, or minus one if some node is still unreached. It's O((V plus E) log V) time and O(V plus E) space."
Complexity & Mathematical Proof
O((V + E) log V)
Look at the code: building adj reads the E edges once and dist gets V entries, O(V + E). A pop that is not stale has d == dist[u], and with non-negative weights dist[u] never drops after that, so each node scans adj[u] at most once: E edge checks in total. Each check pushes at most once (only when dist[v] improves), so pq sees at most E + 1 pushes and E + 1 pops. A heap operation on at most E + 1 entries costs O(log E), and log E <= 2 log V because E <= V^2. Total: O(V + E) setup plus O(E log V) heap work, written O((V + E) log V).
O(V + E)
adj holds V + 1 lists with E entries, dist holds V entries, and pq holds at most E + 1 entries at once, since each push comes from one edge check. There is no recursion. The answer is one integer.
T(V, E) = (V + E) setup + E edge checks + (E + 1) pushes and pops * O(log V) = O((V + E) log V)
Derivation Progression
adj = [[] for _ in range(n + 1)], dist over 1..n: O(V); for u, v, w in times: O(E)
Every edge is stored once in its source's list.
if d > dist[u]: continue skips every pop but the one with d == dist[u]: E edge checks in total
With non-negative weights dist[u] is final once popped, so adj[u] is scanned once.
at most E + 1 heappush and E + 1 heappop, O(log E) = O(log V) each
A push happens only when dist[v] improves, at most once per edge check; log E <= 2 log V.
max(dist.values()): O(V)
The largest settled time, or -1 if some node is still infinite.
Variable Definitions
Number of nodes, n
Number of directed edges, len(times)
Memory Architecture & Bounds
O(1): no recursion
O(V + E): adj (E entries), dist (V entries) and pq (at most E + 1 entries)
O(1): one integer
Boundary Best / Worst Cases
when the source has no outgoing edge: dist and adj are still built, and pq pops once.
.
when many edges improve a dist and push, so pq grows toward E entries.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: Bellman-Ford's relaxations are fine here (), but road and computer networks with millions of nodes need Dijkstra's .
nodes, at most 6000 edges, weights : every edge is checked once, so pq never holds more than entries.
A negative weight (a refund, a credit) silently breaks the settled-means-final rule, so check the input at the boundary. When only one target matters, as in route planning, stop as soon as the target is popped instead of settling every node.
Core Algorithmic State Invariants
- Example 1, Settled in Order
From k = 2: node 2 pops at time 0, nodes 1 and 3 at time 1, node 4 at time 2. Every node is reached, so the answer is the largest time, 2.