510. Bus Routes
A city runs several bus routes. routes[i] lists the stops that bus i visits, over and over, forever — while you are on bus i, you can get off at any stop on its list.
You begin standing at stop source (you are not on any bus) and want to reach stop target, moving only by bus. Boarding a bus counts as taking one bus, and you may transfer at any shared stop.
Your function receives routes, source, and target, and must return the minimum number of buses you have to take to reach the target — or -1 if the target cannot be reached. If source == target, the answer is 0: you are already there.
Example 1:
Input: routes = [[1, 2, 7], [7, 3, 5]], source = 1, target = 5
Output: 2
Explanation: Board bus 0 at stop 1 and ride it to stop 7, where both routes meet. Transfer to bus 1 and ride to stop 5. Two buses in total.
Example 2:
Input: routes = [[1, 9], [3, 5], [4, 5, 6]], source = 1, target = 6
Output: -1
Explanation: From stop 1 only bus 0 is boardable, and it visits stops 1 and 9 only. It shares no stop with the other routes, so stop 6 is unreachable.
Constraints:
- 1 ≤ routes.length ≤ 500
- 1 ≤ routes[i].length ≤ 10⁵, and the total number of stops across all routes is at most 10⁵
- 0 ≤ routes[i][j] < 10⁶
- 0 ≤ source, target < 10⁶
Hints:
The cost being minimized is *buses boarded*, not stops passed — so the natural BFS nodes are the routes themselves, and two routes are adjacent whenever they share a stop.
Build a hash map from each stop to the list of routes serving it. Start a BFS from every route that serves `source` (each costs 1 bus); when you dequeue a route, expand to every unvisited route reachable through any of its stops. Handle `source == target` before all of this — it needs 0 buses.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: routes = [[1, 2, 7], [7, 3, 5]], source = 1, target = 5
Expected output: 2