Bus Routes
Last Updated: March 28, 2026
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, and we want to minimize the number of buses we take. Notice the question is about the number of buses, not the number of stops we pass through.
This is a shortest path problem, but with a twist. We are not counting edges between stops. We are counting how many times we switch buses. Riding one bus for 20 stops counts as 1, but hopping on a second bus to travel 1 stop counts as 2. So the "cost" is per bus, not per stop.
The key observation is that any stop reachable on the same bus route costs nothing extra once you have boarded that bus. So the real question becomes: what is the minimum number of routes we need to chain together to get from source to target? Two routes are "connected" if they share at least one common stop, because at that shared stop we can transfer from one bus to the other.
Key Constraints:
1 <= routes.length <= 500-> The number of bus routes is moderate. Building a route-level graph with O(N^2) edges is feasible (at most 250,000 pairs).sum(routes[i].length) <= 10^5-> The total number of stop entries across all routes is at most 100,000. This is the real bottleneck for stop-level approaches.0 <= routes[i][j] < 10^6-> Stop IDs can be up to a million, so we cannot use a simple array indexed by stop. We need a hash map.
Approach 1: BFS on Stops
Intuition
The most natural first instinct is to treat each bus stop as a node and run a standard BFS from source to target. Two stops are connected if they belong to the same bus route. Since riding one bus from any stop to any other stop on the same route costs 1 bus, we can set up the BFS so that taking one bus expands to all stops on the current route.
The straightforward way to do this: for each stop we dequeue, find all routes that serve it. For each of those routes, add all unvisited stops to the queue. Every time we board a new route from a new stop, that counts as one more bus.
This works correctly, but notice the potential pitfall. If a single route has 100,000 stops, we are iterating through all of them every time we encounter that route. We might also re-encounter the same route from different stops. Without careful bookkeeping, we will do a lot of redundant work. The key optimization is to track visited routes so that once we expand a route's stops, we never do it again.
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, iterate through all its stops.
- If any stop is the target, return the current bus count.
- Add all unvisited stops to the next level's queue and mark them visited.
- Mark the route as visited so we never process it again.
- If the queue empties without reaching the target, return -1.
Example Walkthrough
Code
- Time Complexity: O(N * S) where N is the number of routes and S is the total number of stops across all routes. Building the stop-to-routes map takes O(S). The BFS processes each route at most once, iterating through all its stops. The total work across all route expansions is O(S).
- Space Complexity: O(N * S) for the stop-to-routes map, the visited sets, and the BFS queue. The visited stops set can hold up to S entries.
This approach works correctly and has the right time complexity, but the queue holds individual stops (up to 100,000 entries) and the logic mixes two levels of abstraction. Since we are counting buses, what if we made routes the first-class citizens of our BFS instead?
Approach 2: BFS on Routes (Optimal)
Intuition
Here is the mental shift that makes this problem cleaner. Instead of doing BFS on individual stops, do BFS on routes. Find all routes that contain the source stop, those are reachable with 1 bus. For each of those routes, check if any of their stops is the target. If not, find all routes that share a stop with the current routes (transfer opportunities), those are reachable with 2 buses. Keep expanding until we find a route containing 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 is the BFS level at which we first reach a route containing the target. The queue now holds route indices (at most 500) instead of stop IDs (up to a million), and the logic is more direct: we are literally counting buses, one per BFS level.
BFS guarantees the shortest path in an unweighted graph. By treating routes as nodes and "shared stops" as edges, each BFS level corresponds to exactly one additional bus ride. The first time we reach a route containing the target, we have found the minimum number of buses.
The visited-routes check ensures we never process the same route twice. And because we mark routes as visited the moment we add them to the queue (not when we dequeue them), we avoid adding duplicates and keep the queue size bounded.
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) where N is the number of routes and S is the total number of stops across all routes. Building the stop-to-routes map is O(S). The BFS processes each route at most once, and for each route it iterates through all its stops. The total work is bounded by S.
- 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).