Bus Routes
Understanding the Problem
We have a city with bus stops and bus routes. Each bus route is a loop that visits a specific set of stops. We start at a particular stop and want to reach another stop using as few buses as possible. The answer counts buses boarded, not stops passed through.
This is a shortest path problem where the cost is per bus, not per stop. Riding one bus for 20 stops costs 1, while boarding a second bus to travel a single stop raises the total to 2.
Once you board a bus, every stop on its route is reachable at no extra cost. The question then becomes: what is the minimum number of routes we need to chain together to get from source to target? Two routes can be chained if they share at least one stop, because that shared stop is where we transfer from one bus to the other.
Key Constraints:
1 <= routes.length <= 500-> The number of routes is small. A BFS whose nodes are whole routes searches at most 500 nodes.sum(routes[i].length) <= 10^5-> The total number of stop entries across all routes is at most 100,000. This bounds the work of any approach that scans route contents.0 <= routes[i][j] < 10^6-> Stop IDs can be up to a million, so we map stops to routes with a hash map rather than an array indexed by stop ID.
Approach 1: BFS on Stops
Intuition
Treat each bus stop as a node and run a BFS from source to target. Two stops are connected if some bus route contains both, and riding that bus from one stop to the other costs 1 bus. A single BFS step should therefore expand from a stop to every stop on every route that serves it.
For each stop we dequeue, find all routes that serve it, then add every unvisited stop on those routes to the queue. Each BFS level corresponds to boarding one more bus.
One hazard remains. A route can hold up to 100,000 stops, and the same route can be reached from many different stops, so re-expanding it on every encounter repeats that work. Tracking visited routes ensures each route's stops are expanded once, which keeps the total expansion work bounded by the total number of stop entries.
Algorithm
- If source equals target, return 0 immediately.
- Build a map from each stop to the list of route indices that serve it.
- Initialize a BFS queue with the source stop. Set the initial bus count to 0.
- Maintain a set of visited stops and a set of visited routes.
- For each level of BFS (one level = one bus ride):
- For each stop in the current level, find all routes serving that stop.
- For each unvisited route, mark it visited and iterate through its stops.
- If any stop is the target, return the current bus count.
- Add each unvisited stop to the next level's queue and mark it visited.
- If the queue empties without reaching the target, return -1.
Example Walkthrough
Code
- Time Complexity: O(S) where S is the total number of stop entries across all routes. Building the stop-to-routes map takes O(S). Each stop is dequeued at most once and its route list is scanned once; the sum of all those list lengths is S. Each route is expanded at most once, and the sum of all route lengths is also S.
- Space Complexity: O(S + N) where N is the number of routes: O(S) for the stop-to-routes map, the visited-stops set, and the queue, plus O(N) for the visited-routes set.
This approach is correct and fast, but the queue holds individual stops (up to 100,000 entries) while the answer counts buses. The next approach makes routes the nodes of the BFS, so the search operates directly on the quantity being minimized.
Approach 2: BFS on Routes (Optimal)
Intuition
Run the BFS over routes instead of stops. Every route that contains the source stop is reachable with 1 bus. If any of those routes contains the target, the answer is 1. Otherwise, every route that shares a stop with one of them is reachable with 2 buses, because the shared stop is a transfer point. Expanding level by level finds the first route that contains the target.
This is a standard BFS where the nodes are route indices and two routes are neighbors if they share at least one stop. The number of buses equals the BFS level at which a route containing the target first appears. The queue now holds route indices (at most 500) instead of stop IDs (up to a million), and one BFS level corresponds to one bus.
BFS on an unweighted graph reaches every node at its minimum distance first, so the first route found to contain the target gives the minimum bus count. This is also why marking a route visited at enqueue time (rather than at dequeue time) is safe: any later path to that route uses at least as many buses. Enqueue-time marking also keeps each route in the queue at most once, so the queue never holds more than N entries.
Algorithm
- If source equals target, return 0 immediately.
- Build a map from each stop to the list of route indices that serve it.
- Create a set of "target routes" (routes that contain the target stop) for quick lookup.
- Initialize the BFS queue with all route indices that serve the source stop. Mark them as visited. Set bus count to 1.
- For each level of BFS:
- For each route in the current level, check if it is a target route. If yes, return the current bus count.
- Otherwise, iterate through all stops on this route. For each stop, find all other routes that serve it. Add any unvisited routes to the next level's queue.
- If the queue empties, return -1.
Example Walkthrough
Code
- Time Complexity: O(N S) in the worst case, where N is the number of routes and S is the total number of stop entries across all routes. Building the stop-to-routes map is O(S). The BFS processes each route at most once, and processing a route scans the route list of every stop on it. A stop shared by many routes is rescanned once per route that contains it, which bounds the total at N S. With N <= 500 and S <= 10^5, this stays within roughly 5 * 10^7 operations.
- Space Complexity: O(N + S) for the stop-to-routes map (S entries), the visited array (N entries), and the BFS queue (at most N route indices).