Watch 10 video solutions for Bus Routes, a hard level problem involving Array, Hash Table, Breadth-First Search. This walkthrough by Pepcoding has 19,247 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Example 2:
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 Output: -1
Constraints:
1 <= routes.length <= 500.1 <= routes[i].length <= 105routes[i] are unique.sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106Problem Overview: You are given several bus routes where each route repeats forever. Each route contains a list of bus stops. Starting from a source stop, determine the minimum number of buses you must take to reach a target stop.
Approach 1: Graph BFS on Routes (O(N * K) time, O(N * K) space)
The key idea is to treat each bus route as a node in a graph. Two routes are connected if they share at least one common stop. Instead of explicitly building the entire route graph, build a stop → list of routes mapping using a hash table. Start a Breadth-First Search from all routes containing the source stop. Each BFS level represents taking one additional bus. For every stop on the current route, look up other routes passing through that stop and push them into the queue if not visited. Stop when any route contains the target stop. This approach works well because BFS naturally finds the minimum number of bus transfers.
Approach 2: Bidirectional BFS (O(N * K) time, O(N * K) space)
Bidirectional BFS speeds up search when the graph is large. Instead of exploring only from the source, run BFS simultaneously from both the source stop and the target stop. Maintain two frontiers and expand the smaller one at each step. The same stop → routes mapping is used to discover neighboring routes. When the two searches meet at a common route or stop, you have found the minimum number of buses required. Because both sides explore fewer nodes, the practical runtime is often significantly lower than a single BFS.
Both approaches rely heavily on fast stop lookups and queue-based traversal, which makes arrays for route storage and hash maps for indexing stops the most efficient structure combination.
Recommended for interviews: The standard graph BFS approach is what most interviewers expect. It shows that you can transform the problem into a graph traversal and use BFS to compute the shortest path in terms of bus transfers. Bidirectional BFS is an optimization that demonstrates deeper graph-search knowledge and can be mentioned after presenting the core BFS solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph BFS on Routes | O(N * K) | O(N * K) | General case. Clean and widely accepted interview solution for finding minimum bus transfers. |
| Bidirectional BFS | O(N * K) | O(N * K) | Large search spaces where exploring from both source and target reduces traversal depth. |