Bus Routes
hardTime: O(V + E)Space: O(V + E)
Recognize the pattern
minimum buses from source to targetBFS on routes not stopsroute connectivity
Brute force idea
BFS on stops — slow for large route networks.
Better approach
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).
Key invariant
Each BFS step = one bus ride. Routes connect via shared stops. First time reaching a route containing the target = minimum buses.
Watch out for
BFS on stops — too many nodes. BFS on routes is much more efficient.