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 < 106The #815 Bus Routes problem can be modeled as a graph traversal task. Instead of viewing each stop independently, think of each bus route as a node in a graph. Two routes are connected if they share at least one common stop. The goal is to determine the minimum number of buses required to travel from the source stop to the target stop.
A common strategy is to build a mapping from bus stop to the list of routes that serve it using a hash table. Starting from the source stop, perform a Breadth-First Search (BFS) across routes. Each BFS level represents taking one additional bus. As you visit routes, explore all stops they serve and enqueue new routes connected through those stops while marking visited routes to avoid cycles.
This approach ensures the shortest number of bus transfers because BFS explores possibilities level by level. Efficient use of hash maps and visited sets helps keep the search manageable even when many routes and stops are present.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS with stop-to-route hash map | O(N * K) | O(N * K) |
NeetCode
In this approach, we treat the problem as a graph where each bus route is a node and bus stops are edges connecting these nodes. We will perform a Breadth-First Search (BFS) starting from the source and try to reach the target while counting the number of buses required. The BFS helps in finding the shortest path in terms of the number of bus routes.
Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route.
Space Complexity: O(N * D) for storing the graph.
1from collections import defaultdict, deque
2
3def numBusesToDestination(routes, source, target):
4 if source == target:
5 return 0
6
7 stop_to_routes = defaultdict(set)
8 for i, route in enumerate(routes):
9 for stop in route:
10 stop_to_routes[stop].add(i)
11
12 queue = deque([(source, 0)]) # (current_stop, buses_taken)
13 visited_stops = {source}
14 visited_routes = set()
15
16 while queue:
17 stop, buses = queue.popleft()
18 for route in stop_to_routes[stop]:
19 if route in visited_routes:
20 continue
21 visited_routes.add(route)
22 for next_stop in routes[route]:
23 if next_stop == target:
24 return buses + 1
25 if next_stop not in visited_stops:
26 visited_stops.add(next_stop)
27 queue.append((next_stop, buses + 1))
28
29 return -1This code uses Breadth-First Search (BFS) to explore the given routes. A queue is utilized to manage bus stops, beginning at the source, and systematically visit every possible stop until the target is achieved or all possibilities are exhausted. The unique bus stops and routes are tracked to prevent repetition. When the target stop is reached, the code returns the count of buses needed to reach that spot. If the target is unreachable, it returns -1.
For optimization, we can leverage a bidirectional BFS. This technique reduces the breadth by simultaneously exploring from both the source and the target and meeting in the middle. A dual directional expansion can therefore lead to faster convergence in finding the solution.
Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route.
Space Complexity: O(N * D) for storing the graph and queue data structures.
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <queue>
5
using namespace std;
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
if (source == target) return 0;
unordered_map<int, vector<int>> stop_to_routes;
for (int i = 0; i < routes.size(); ++i) {
for (int stop : routes[i]) {
stop_to_routes[stop].push_back(i);
}
}
unordered_set<int> visited_source, visited_target;
queue<pair<int, int>> q_source, q_target;
q_source.push({source, 0});
visited_source.insert(source);
q_target.push({target, 0});
visited_target.insert(target);
while (!q_source.empty() && !q_target.empty()) {
int res = -1;
if (q_source.size() <= q_target.size()) {
res = bfs(routes, stop_to_routes, visited_source, visited_target, q_source);
} else {
res = bfs(routes, stop_to_routes, visited_target, visited_source, q_target);
}
if (res != -1) return res;
}
return -1;
}
private:
int bfs(const vector<vector<int>>& routes, unordered_map<int, vector<int>>& stop_to_routes,
unordered_set<int>& visited_this, unordered_set<int>& visited_other, queue<pair<int, int>>& q) {
int count = q.size();
while (count-- > 0) {
auto [stop, buses] = q.front(); q.pop();
for (int route : stop_to_routes[stop]) {
for (int next_stop : routes[route]) {
if (visited_other.count(next_stop)) return buses + 1;
if (visited_this.insert(next_stop).second) {
q.push({next_stop, buses + 1});
}
}
}
}
return -1;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Bus Routes is considered a challenging graph traversal problem and has appeared in technical interview preparation sets for companies like Google and Amazon. It tests understanding of BFS, graph modeling, and efficient use of hash maps.
BFS is ideal because the problem asks for the minimum number of buses required. BFS naturally explores all possibilities in increasing order of steps, ensuring the first time the target is reached corresponds to the fewest bus transfers.
The optimal approach uses Breadth-First Search (BFS). By mapping each bus stop to the routes that pass through it, you can explore routes level by level, where each level represents taking one additional bus. This guarantees finding the minimum number of buses needed to reach the destination.
A hash map and a queue are the key data structures. The hash map stores the mapping from bus stops to routes, while the queue is used for BFS traversal. Visited sets help prevent revisiting the same routes or stops.
This C++ implementation uses bidirectional BFS to improve time efficiency by concurrently working from both the forward and backward directions. It alternately expands from the queue with fewer elements, using a shared graph or set to determine intersections, which indicates the optimal path. By operating in both directions, this reduces redundant processing and ensures convergence happens faster compared to one-sided BFS.