Leetcode 815. Bus Routes

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.

Hint 1: Graph Modeling Think of this problem as a graph traversal. What should the nodes represent? Consider treating each bus route as a node rather than each stop. Two route nodes are connected if they share at least one common stop.

Hint 2: Search Strategy Once you've modeled routes as nodes in a graph, you need to find the shortest path from any route containing the source to any route containing the target. What algorithm is best suited for finding the shortest path in an unweighted graph?

Hint 3: Optimization To efficiently find which routes share common stops, build a mapping from each stop to all routes that visit it. This preprocessing step will help you quickly identify which routes you can transfer to from your current route.

Full Solution `` Solution Explanation:

The key insight is to treat bus routes as nodes in a graph rather than individual stops. Two routes are connected if they share at least one common stop (transfer point).

Algorithm:

1. Preprocessing: Build a mapping from each stop to all routes that visit it. This allows us to quickly find transfer opportunities.

2. BFS Search: We perform breadth-first search starting from all routes that contain the source stop. BFS guarantees we find the shortest path (minimum transfers).

3. State Tracking:

   • Track visited routes to avoid cycles
   • Track visited stops to avoid redundant processing
   • Each BFS level represents one additional bus taken

4. Early Exit: As soon as we encounter the target stop on any route we're exploring, we return the current bus count.

Time Complexity: O(N * S) where N is the number of routes and S is the total number of stops across all routes. In the worst case, we visit each route once and process all its stops.

Space Complexity: O(N * S) for the stop-to-routes mapping and visited sets.

This approach is efficient because it focuses on route-level transfers rather than exploring every possible stop-to-stop path, which would be much slower for large networks.