Network Delay Time medium
Description
You are given a network of n nodes labeled from 1 to n. You are given times, a list of travel times as directed edges times[i] = (u_i, v_i, w_i) where u_i is the source, v_i is the target, and w_i is the time it takes for a signal to travel from u_i to v_i.
A signal is sent from node k. Return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.
Examples
> Case 1:
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: from 2 → 1 (t=1), 2 → 3 (t=1), 3 → 4 (t=2). Max = 2.
> Case 2:
times = [[1,2,1]], n = 2, k = 1
Output: 1
> Case 3:
times = [[1,2,1]], n = 2, k = 2
Output: -1 # node 1 unreachableConstraints
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= u_i, v_i <= n,u_i != v_i0 <= w_i <= 100
State design
Pure single-source shortest path. Weights are non-negative → Dijkstra.
The twist: the answer is not any single dist[v], it’s max(dist[v]) across all v — the signal arrives “everywhere” only when the slowest node receives it.
If any vertex is unreachable, dist[v] = ∞, and the answer is -1.
Code
Analysis
- Time:
O((V + E) log V)— standard Dijkstra. - Space:
O(V + E).
“Return the time for all nodes” → take the max of all distances, not the sum. Misreading “all” as “sum” is a classic off-the-cuff mistake.
Same skin
- Shortest path in a weighted directed graph — strip the “max” and you’re back to vanilla Dijkstra.
- Path with Minimum Effort — same skeleton, replace
+withmaxin the relaxation. - Minimum Cost to Reach Destination in Time — Dijkstra with a constraint, similar shape.