The problem
Junctions 1 to n are connected by one-way roads with travel times (times[i] = (u, v, w)). A signal starts at junction k. Return how long until every junction has received it (the largest of the fastest times), or −1 if some junction can never be reached.
Input: times = [[1,2,4], [1,3,1], [3,2,2], [2,4,1], [3,4,5], [4,5,3]], n = 5, k = 1 Output: 7 (junction 5 is last: 1 → 3 → 2 → 4 → 5)
Picture it
Picture a city map: pins are junctions, roads are labelled with minutes. Each pin shows its best known time (∞ at first). We always “lock in” the unfinished pin with the smallest time, because no route through farther pins could beat it. From that pin we check each road: if going through it is faster, update the neighbour’s time.
How to recognise it
- A weighted directed graph (one-way roads with travel times) and a single starting point.
- The question needs the shortest time from the start to every node, then a summary of those times (here, the largest).
- All weights are non-negative, so a path never gets cheaper by going further.
- With up to 100 nodes and 6,000 roads you want near-linear work in the number of roads.
Start with brute force
The first idea, trying every path from the start, is exponential. A simple fix is to keep a best-known time for every junction and keep relaxing every road (setting dist[v] = dist[u] + w whenever that is smaller) until a full pass changes nothing.
def network_delay_brute(times, n, k):
dist = [inf] * (n + 1)
dist[k] = 0
changed = True
while changed:
changed = False
for u, v, w in times:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
m = max(dist[1:])
return -1 if m == inf else m
Each pass costs O(E), and up to n passes may be needed, so time is O(V·E): about 6 × 10^5 steps for 100 nodes and 6,000 roads, which is fast enough here, but about 10^10 for 10^5 nodes and roads. Space is O(V). This works because of the non-negative weights.
From brute force to the idea
- Find the waste. The brute force relaxes every road on every pass, including roads whose start junction has not improved since last time.
- Settle the closest first. If all times are non-negative, the unsettled junction with the smallest tentative time cannot be improved later, because any other route to it would pass through something at least as far away.
- Use a min-heap.
pqholds(time, junction). Popping gives the closest junctionuwith its timed. - Relax only its roads. For each road
(v, w)fromu, ifd + wbeats the best known time forv, record it and push(d + w, v). - Skip stale entries. A junction can be pushed more than once. If the popped
dis larger thandist[u], a better entry was already processed, socontinue. - Answer. If fewer than n junctions were reached, someone never hears, so return -1. Otherwise the signal reaches everyone when the slowest junction hears it:
max(dist.values()).
The key idea: always finalise the nearest unsettled junction, then relax only its outgoing roads.
The key idea
Dijkstra: a min-heap of (time, junction); pop the closest, relax its roads. Works when no road has negative time.
Python solution
def network_delay_time(times, n, k):
roads = defaultdict(list)
for u, v, w in times: # one-way
roads[u].append((v, w))
dist = {k: 0}
pq = [(0, k)]
while pq:
d, u = heappop(pq) # closest
if d > dist[u]:
continue
for v, w in roads[u]:
if d + w < dist.get(v, inf):
dist[v] = d + w
heappush(pq, (dist[v], v))
if len(dist) < n:
return -1 # someone never hears
return max(dist.values())LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict from heapq import heappush, heappop from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Repeated relaxation (brute force) | O(V·E): up to V passes over all roads | O(V): the distance list |
| Dijkstra with a heap (shown code) | O(E log V): each road causes at most one push, and each push or pop costs O(log V) | O(V + E): the road lists, the distance dictionary and the heap |
Edge cases
- One junction (
n = 1, no roads,k = 1): returns 0. - A junction the signal cannot reach (
n = 2,[[1,2,1]],k = 2): returns -1, because the roads are one-way. - Two routes (
[[1,2,1],[2,3,2],[1,3,4]],k = 1): returns 3, the faster route through junction 2. - Zero-time roads are fine:
[[1,2,0],[2,1,0]]returns 0. - Negative times: not supported, because a settled junction could later be improved. Use Bellman-Ford for those.
- Imports:
heappushandheappopfromheapq,inffrommath, anddefaultdict. Junctions are numbered from 1.
Common mistakes
- Using BFS, which counts roads, not time.
- Returning the sum of the times instead of the largest.
- Forgetting the -1 check, so unreachable junctions are ignored.
- Missing the stale-entry check, which still gives the right answer but processes entries needlessly.
- Treating the roads as two-way when they are one-way.
Return how many junctions receive the signal within time T (the start counts). Describe what changes, then write it if you like.
Compare with our answer
Run the same Dijkstra, but stop as soon as the closest remaining entry is later than T. Pops come out in non-decreasing time, so everything after that is also too late.
def reached_within(times, n, k, T):
roads = defaultdict(list)
for u, v, w in times:
roads[u].append((v, w))
dist = {k: 0}
pq = [(0, k)]
while pq:
d, u = heappop(pq)
if d > T:
break
if d > dist[u]:
continue
for v, w in roads[u]:
if d + w < dist.get(v, inf):
dist[v] = d + w
heappush(pq, (dist[v], v))
return sum(1 for d in dist.values() if d <= T)
Time O(E log V), space O(V + E).
A strong answer mentions: stopping early once the popped time exceeds T, why pop order makes that safe, and counting the junctions whose final time is at most T.
1. A map has roads with lengths in kilometres, all greater than zero. You must find the shortest distance from your home to every other town. Which approach fits best?
Dijkstra gives the shortest weighted distance to every node when weights are non-negative. BFS counts roads, not kilometres, and a spanning tree does not give shortest routes.
2. Why does the shown code have if d > dist[u]: continue after popping?
A junction may be pushed several times as shorter routes are found. The first pop is the best, and later pops carry a larger d than dist[u], so they are stale. The heap can still hold several entries per junction.
3. A learner deletes the lines if len(dist) < n: return -1. Which input now returns a wrong answer?
Without the check, a signal that cannot reach every junction returns the largest time among those it did reach (0 here). In the other inputs every junction is reached, so the check never fires.
Score 60% or more and the lesson is marked complete.