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.
routes[i] is the list of stops served by the i-th bus route.source and target representing the starting and ending stops.target from source, or -1 if unreachable.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
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.