Practice/PayPal/Leetcode 815. Bus Routes

Leetcode 815. Bus Routes

CodingMust

Problem

You are given a transit network represented by an array of bus routes. Each bus route is a list of stops that the bus visits. Buses follow their routes in a circular pattern, meaning you can board at any stop on the route and get off at any other stop on the same route.

Given a starting stop and a destination stop, determine the minimum number of buses you must take to travel from the source to the target. If it's impossible to reach the target, return -1.

Requirements

1. Each route is represented as an array of stop IDs that the bus visits
2. You can board any bus at any stop it visits
3. You can transfer between buses at stops where their routes overlap
4. Return the minimum number of buses needed, or -1 if unreachable
5. If you're already at the target stop, return 0

Constraints

• 1 ≤ routes.length ≤ 500
• 1 ≤ routes[i].length ≤ 10^5
• All stops on a route are unique
• 0 ≤ source, target < 10^6
• The total number of stops across all routes is at most 10^5

Examples

Example 1:

Input: routes = [[1, 2, 7], [3, 6, 7]], source = 1, target = 6 Output: 2 Explanation: Take the first bus (route [1, 2, 7]) from stop 1 to stop 7. Then transfer to the second bus (route [3, 6, 7]) and ride to stop 6. Total buses taken: 2

Example 2:

Input: routes = [[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]], source = 15, target = 12 Output: 3 Explanation: One possible path requires 3 bus transfers to get from stop 15 to stop 12.

Example 3:

Input: routes = [[1, 2, 3], [4, 5, 6]], source = 1, target = 6 Output: -1 Explanation: There's no way to travel from stop 1 to stop 6 since the routes don't connect.