Example 1
ready- Input
times = [ [ 2, 1, 1 ], [ 2, 3, 1 ], [ 3, 4, 1 ] ] n = 4 k = 2- Expected
2- Why
- node 4 receives the signal last, at time 2
Network Delay Time
35 min · networkDelayTime()mediumOpen in LeetCode #743 ↗
One server sends an alert. How long until the slowest machine in the network hears it?
You receive n nodes numbered from 1 through n and a list times. Each entry
[u, v, w] describes a directed edge — a one-way connection from u to v that
takes w units of time to cross. A signal starts at node k at time 0.
Return the first time by which every node has received the signal. The signal follows
the fastest available route to each node, so your answer is the largest of those
fastest arrival times. Return -1 when even one node can't be reached from k.
A connection may point from a node back to itself. No directed pair appears more than once, and every travel time is positive.
Constraints
1 <= n <= 1001 <= times.length <= 6_000- Every
times[i]is[u, v, w]with1 <= u, v <= nand1 <= w <= 100. - Directed pairs
(u, v)are distinct. 1 <= k <= n
Hints
What does each arrival need?
You need the shortest travel time from one source, k, to every node. Once you
have those distances, the answer is their maximum — unless one is still infinite.
Use the positive weights
Every edge costs at least 1. That makes Dijkstra's algorithm a fit: repeatedly
finalize the unreached node with the smallest known arrival time.
Stale queue entries are harmless
When a shorter route is found, push the new distance. If an older, larger entry comes out later, compare it with the current best distance and skip it.
Follow-up
How would your choice change if some travel times could be negative, while negative cycles were still forbidden?
Visible cases
Examples
Example 2
ready- Input
times = [ [ 1, 2, 5 ] ] n = 3 k = 1- Expected
-1- Why
- node 3 has no route from the source
Example 3
ready- Input
times = [ [ 1, 1, 100 ] ] n = 1 k = 1- Expected
0- Why
- the only node has the signal at time 0
Interview signal
Asked at
AmazonGoogle
Bellman-Ford — relax every edge in rounds
Relaxing an edge means using a known route to u to improve the best known route
to v. Bellman-Ford repeats that check across every edge. After round r, every
shortest route using at most r edges has been accounted for, so n - 1 rounds are
enough when all useful routes are cycle-free.
Bellman-Ford is a sturdy baseline because it works even with negative edge weights. Here, though, it scans the whole edge list again and again despite every weight being positive.
def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
distances = [float("inf")] * (n + 1)
distances[k] = 0
for _ in range(n - 1):
next_distances = distances.copy()
for source, target, travel_time in times:
candidate = distances[source] + travel_time
if candidate < next_distances[target]:
next_distances[target] = candidate
if next_distances == distances:
break
distances = next_distances
answer = max(distances[1:])
return -1 if answer == float("inf") else int(answer)Time O(VE) — up to V - 1 passes over all E edges. Space O(V) for the two
distance arrays.
Dijkstra's algorithm — expand the earliest arrival
Dijkstra is the right algorithm because this is a single-source shortest-path problem and every edge weight is non-negative. Keep each node's best arrival time in a min-heap. The smallest queued time comes out first; no later detour through positive-weight edges can improve a node once that smallest time is current.
import heapq
def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
for source, target, travel_time in times:
graph[source].append((target, travel_time))
distances = [float("inf")] * (n + 1)
distances[k] = 0
queue = [(0, k)]
while queue:
elapsed, node = heapq.heappop(queue)
if elapsed != distances[node]:
continue
for neighbor, travel_time in graph[node]:
candidate = elapsed + travel_time
if candidate < distances[neighbor]:
distances[neighbor] = candidate
heapq.heappush(queue, (candidate, neighbor))
answer = max(distances[1:])
return -1 if answer == float("inf") else int(answer)The stale-entry check matters: pushing an improved distance is cheap, and ignoring the older heap entry avoids needing a decrease-key operation.
Time O(E log V) with a binary heap. Space O(V + E) for the graph, distances, and heap.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
2
Run: visible + custom · Submit: full suite