Find the minimum number of bus rides needed to travel from a source stop to a target stop using a set of circular bus routes.
You are given a list of bus routes. Each route is a sequence of stops that one bus repeatedly visits in a cycle.
Starting from a given stop, you may board any bus whose route contains your current stop. While riding that bus, you can move to any other stop on the same route. You may transfer to another bus only at a stop that appears on both routes.
Return the minimum number of buses you must take to travel from the source stop to the target stop. If it is impossible, return -1.
A bus route is considered cyclic, so after the last stop it continues again from the first stop.
Input Format
- An integer array of routes, where
routes[i]is the list of stops served by the i-th bus route. - Two integers
sourceandtargetrepresenting the starting and ending stops.
Output Format
- Return a single integer: the minimum number of buses needed to reach
targetfromsource, or-1if unreachable.
Constraints
- Each route contains one or more stops.
- Stops may appear in multiple routes.
- You may board a bus only at a stop served by that bus.
- You may transfer buses only at shared stops.
- Treat each bus ride as costing 1, regardless of how many stops you travel on that bus.
Example 1
Input
routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output
2
Explanation
Take the first bus from stop 1 to stop 7, then transfer to the second bus and continue to stop 6.
Example 2
Input
routes = [[1,2,3],[3,4,5],[5,6,7]], source = 1, target = 7
Output
3
Explanation
One possible path is 1 -> 3 using the first bus, then 3 -> 5 using the second bus, then 5 -> 7 using the third bus.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.