Lenpaste

About

Docs

Settings

markdown, LF
 1# LC5441 Bus Routes — BFS over Routes, Not Stops
 2
 3**Approach.** Map stop→routes; BFS where each level is one more bus taken; mark routes visited so each route expands once.
 4
 5```python
 6from collections import defaultdict, deque
 7def numBusesToDestination(routes, S, T):
 8    if S == T: return 0
 9    by = defaultdict(list)
10    for i, r in enumerate(routes):
11        for s in r: by[s].append(i)
12    seen_r, seen_s, q = set(), {S}, deque([(S, 0)])
13    while q:
14        s, d = q.popleft()
15        for ri in by[s]:
16            if ri in seen_r: continue
17            seen_r.add(ri)
18            for n in routes[ri]:
19                if n == T: return d + 1
20                if n not in seen_s: seen_s.add(n); q.append((n, d + 1))
21    return -1
22```
23
24**Interview note.** Say the invariant out loud before coding, then test an edge case. Practise these patterns with an [Linkjob AI](https://www.linkjob.ai/) — more at https://www.linkjob.ai/ .

Created: Sat, 07 Nov 2026 05:25:18 +0000

Expires: Never