AdvancedGraphsHeaps
Network Delay Time
Problem
You are given a network of n nodes labelled 1 … n and a list of directed edges times[i] = [u, v, w] meaning a signal sent from u reaches v after w units of time. A signal is sent from node k. Return the minimum time for all nodes to receive the signal, or -1 if it is impossible for every node to receive it.
Constraints
- 1 ≤ k ≤ n ≤ 100
- 1 ≤ times.length ≤ 6000
- 0 ≤ w ≤ 100
- no self-edges or duplicate edges
Examples
in: n = 4, k = 2, times = [[2,1,1],[2,3,1],[3,4,1]]
out: 2
Node 4 is reached last at time 2 via 2 → 3 → 4.
in: n = 2, k = 1, times = [[1,2,1]]
out: 1
What this tests
- Recognising single-source shortest paths with non-negative weights
- Dijkstra with a lazy priority queue (skip stale entries)
- Why BFS is insufficient with weights and why Dijkstra needs non-negative edges
- Knowing when to switch to Bellman-Ford or Floyd-Warshall
- Turning "time for all to receive" into "max of shortest distances"
Pattern RecognitionComplexity AnalysisSystematic ReasoningImplementationEdge Cases
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Some edge weights can be negative (say, a "time credit" on certain links). What breaks and what do you use?
F2
All edge weights are 1. Can you do better than Dijkstra?
F3
You need the delay from *every* node to every other node.
F4
Find the time at which all nodes have received the signal if each node can only forward once it has received from *all* its in-neighbours.