Problem Statement
Bus Routes
You are given a list of bus routes. Each route is the list of stops one bus drives in a loop, so routes[i] is the stops that bus number i visits. You start at a stop called source and want to reach a stop called target. The question is, what is the fewest number of buses you need to ride to get there? If it is impossible, the answer is -1. The key trick is to think of each whole bus route as one thing you can hop onto, and two routes are connected if they share a stop (because you can switch from one bus to the other at that shared stop). We use a search called BFS, breadth-first search, which is like dropping a stone in a pond and watching the ripples spread out evenly. BFS checks everything one bus away first, then everything two buses away, and so on, so the first time it reaches the target it has used the fewest buses. We ripple out over routes, not individual stops, because there can be a huge number of stops but the routes are what we actually count.
Signals to notice
Brute force first
BFS on stops — slow for large route networks.
The key insight
Build stop→routes map. BFS on routes: start with routes containing source. For each route, check all stops for target. Enqueue connected routes (shared stops). O(sum of route lengths).
Trace it on routes=[[1,2,7],[3,6,7]], source=1, target=6
build stop_to_routes: 1→{0}, 2→{0}, 7→{0,1}, 3→{1}, 6→{1}; visited_stops={1}
seed: source 1 is in route 0 → queue=[(route0,buses1)], visited_routes={0}
pop (route0,1); scan routes[0]=[1,2,7]: stop1 already visited (skip); stop2 new but route{0} seen
still in route0: stop7 new → route1 unvisited → enqueue (route1,buses2), visited_routes={0,1}
pop (route1,2); scan routes[1]=[3,6,7]: stop3 new, no new routes
still in route1: stop6 == target → return buses = 2What must stay true
Each BFS step = one bus ride. Routes connect via shared stops. First time reaching a route containing the target = minimum buses.
Shape of the loop
build stop_to_routes map (stop -> set of route indices)
seed queue with (route, 1) for every route containing source; mark visited
while queue: route, buses = popleft()
for stop in routes[route]:
if stop == target: return buses
for nextRoute in stop_to_routes[stop] if unvisited: enqueue (nextRoute, buses+1)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
BFS on stops — too many nodes. BFS on routes is much more efficient.