Bus Routes
MediumBFS over routes, not stops
Problem
Given bus routes (each a loop of stops) and a source and target stop, return the fewest buses you must take to reach the target, or -1.
BFS over buses (not stops): each bus you board is one step; the first to reach the target is fewest.
The idea
Model each bus route as a node and connect routes that share a stop, so the answer is the number of routes on a shortest path — which is the number of buses taken. Searching over stops instead makes the graph far denser and the counting much harder.
The trick
- Build a stop -> routes index first so you can find neighbours quickly.
- Mark routes as used, not stops; re-boarding a used route is never helpful.
- The BFS depth is the bus count, starting at 1 for the first route boarded.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — routes=[[1,2,7],[3,6,7]], source=1, target=6 Values: 1, 2, 7.
1map stop -> routes that include it2BFS over routes starting from source's routes3count buses; first time target's route reached = answerInput
- array
- [1, 2, 7]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- routes = [[1,2,7],[3,6,7]], source = 1, target = 6
- Output:
- 2
- Explanation:
- Take bus 0 then bus 1 → 2 buses.
Example 2
- Input:
- routes = [[1,2,7],[3,6,7]], source = 1, target = 2
- Output:
- 1
- Explanation:
- One bus reaches stop 2.
Example 3
- Input:
- routes = [[1,2]], source = 1, target = 5
- Output:
- -1
- Explanation:
- Stop 5 unreachable → -1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.