Network Delay Time
On this page
Problem statement
A network has n nodes labeled 1 to n and directed links
(u, v, w): a signal sent from u reaches v after w time units. A signal starts at node k at time 0. Return the time when every node has received it, or −1 if some node never does. Delays are non-negative.
This is single-source shortest paths in disguise: each node hears the signal at its shortest-path time from k, and the answer is the largest of those. It is the standard way interviewers check that you know Dijkstra's algorithm and why BFS is not enough. Original problem: LeetCode 743.
Example

times = [[1,2,4], [1,3,1], [3,2,2], [2,4,1], [3,5,7], [4,5,2]], n = 5, k = 1
Output: 6
# node 3 at 1, node 2 at 3 (via 3), node 4 at 4, node 5 at 6 (via 2 and 4)
Same links, n = 6, k = 1
Output: -1 # node 6 has no incoming link
Constraints (assumed)
- 1 ≤ n ≤ 100; up to 6,000 links; 0 ≤ w ≤ 100.
What this question tests
- Recognizing single-source shortest paths with non-negative weights.
- Implementing Dijkstra with a min-heap, including stale heap entries.
- Turning "when does everyone hear it" into max of the shortest distances, and handling unreachable nodes.
Questions to ask first
- Can delays be negative? (Here: no. With negatives you'd need Bellman-Ford.)
- Are links one-way? (Here: yes, directed.)
- Can there be several links between the same pair, or self-loops? (Yes; the algorithm handles both.)
- What if some node is unreachable? (Return −1.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.