This practice workspace is built for desktop. Open it on a larger screen to start solving.
Bus Routes
You are given an array routes representing bus routes where routes[i] is a bus route that the i-th bus repeats forever.
- For example, if
routes[0] = [1, 5, 7], this means that the0-th bus travels in the sequence1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...forever.
You will start at the bus stop source (you are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops only by buses.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
If source == target, the answer is 0 (you don't need any bus).
Approach. Build a stop-to-routes index, then BFS over routes (not stops) — each level of the BFS represents boarding one more bus.
Examples
Constraints
- 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
Preview Mode
This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.
Your approach
- Pattern:Breadth-First Search
- Time:O(N)
- Space:O(1)
Complete approach — pattern and complexity both named.
Coach
What you got right
You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.
Where it diverged
No divergence detected. The code correctly aligns with the stated approach.
Next attempt: focus on
Try solving related sliding window problems to build familiarity with two-pointer variants.
Signals
No signals fired — clean run, you stayed in flow.