Bus Routes: Minimum Transfers
routes[i] is the list of stops bus i visits in a loop, forever. You start at stop source (not on a bus) and want to reach stop target. Return the minimum number of buses you must take, or -1 if impossible.
routes = [[1,2,7], [3,6,7]], source = 1, target = 6 => 2 (bus 0 to stop 7, then bus 1 to stop 6) routes = [[7,12], [4,5,15], [6], [15,19], [9,12,13]], source = 15, target = 12 => -1
Up to 500 routes and 100,000 total stops; stop ids can reach 1,000,000.
Hints
Hint 1
The graph to search is routes, not stops: taking a bus is one edge, and you can transfer wherever two routes share a stop.
Hint 2
Build stop → routes once. Start the BFS from every route through the source with distance 1.
Hint 3
After expanding a stop, clear its route list — every stop is expanded at most once, which is what keeps the whole search O(total stops).