DSA problem
Bus Routes
You are given an array routes representing bus routes. routes[i] is a list of stops that bus i visits repeatedly in a cycle. You start at bus stop source (you are not on any bus) and you want to reach bus stop target. You may switch buses freely at any common stop. Return the minimum number of buses you must take, or -1 if it is impossible. If source == target, the answer is 0 because you do not need to take any bus.
This is a subtle BFS modelling problem. The naive approach BFSes over stops with edges between every pair of stops on the same route, but a route with L stops creates L * (L - 1) / 2 edges, easily exploding to billions of edges across many routes.
The clean modelling does BFS over BUSES, not stops. First build a stop -> set of buses map. Then BFS where each "level" represents taking one more bus. Start by enqueuing every bus that serves source; mark those buses as visited so each bus is ridden at most once. For each bus you ride, you can reach any of its stops; from each stop, you can transfer to any bus serving that stop that hasn't been ridden yet.
The first level at which the target stop appears among the stops of a ridden bus is the answer. Because there are at most B buses and total stops S, BFS does O(B + S) work; the level count is bounded by B. This runs in O(N) time and O(N) space, where N is the total size of routes.
Examples
routes = [[1,2,7],[3,6,7]], source = 1, target = 62routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12-1routes = [[1,7],[3,5]], source = 5, target = 50Constraints
- 1 <= routes.length <= 500.
- 1 <= routes[i].length <= 10^5
- All the values of routes[i] are unique.
- sum(routes[i].length) <= 10^5
- 0 <= routes[i][j] < 10^6
- 0 <= source, target < 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.