Bus Routes
On this page
Problem statement
A city has bus routes;
routes[i]lists the stops that bus i visits, and each bus runs its loop forever in both directions. You are at stopsourceand want to reach stoptarget. Return the fewest buses you must board, or −1 if it can't be done. Riding further on a bus you're already on costs nothing; only boarding counts. Ifsource == target, the answer is 0.
Original problem: LeetCode 815. The hard part isn't BFS itself but choosing what a BFS step means: here it's "board one more bus", not "move one stop".
Example

routes = [[1, 4, 7], [7, 9, 12], [12, 15], [4, 20]]
source = 1, target = 15 -> 3 # bus 0, bus 1, bus 2
source = 1, target = 20 -> 2 # bus 0 to stop 4, then bus 3
source = 9, target = 9 -> 0
source = 1, target = 99 -> -1 # no bus stops at 99
Constraints (assumed)
- 1 ≤ number of routes ≤ 500; each route has up to 10⁵ stops; total stops over all routes ≤ 10⁵.
- Stop ids are integers up to 10⁶; a route lists each stop once.
What this question tests
- Modeling: picking buses (routes) as the unit of cost instead of stops.
- A level-by-level BFS that stops as soon as the target appears.
- Avoiding repeated work: marking routes as used, not just stops.
Questions to ask first
- What if source equals target? (Here: 0, even if no bus stops there.)
- Do buses run in both directions? (Here: yes, every stop on a route is reachable from every other.)
- How big can a route be? Long routes make "connect every pair of stops" far too slow.
- Do we need the actual list of buses, or only the count? (Here: only the count.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.