Bus Routes solution and explanation
Google
9 more videos on this problem
Bus Routes | Dry Run | Intuition | UBER | Leetcode-815codestorywithMIK · 21:21 · 14K views
LeetCode 815. Bus RoutesHappy Coding · 21:00 · 10K views
UBER'S #1 INTERVIEW QUESTION | BUS ROUTES | PYTHON BFS SOLUTIONCracking FAANG · 18:03 · 10K views
815. Bus Routes | Tricky BFSAryan Mittal · 19:27 · 9K views
LeetCode 815. Bus Routes Detailed Explanation + Coding (Python)Algorithms Simplified · 31:53 · 4K views
✅ Bus Routes - Modified Bellman Ford Algorithm - Leetcode Hard 815 - Interview Solution - ExplainedLeet Logics · 14:26 · 3K views
Bus Routes - Leetcode 815 - Java - Leetcode Hardcoding interview questions · 17:03 · 2K views
Daily Leetcode #1321: Nov 12, 2023 - 815. Bus RoutesProgramming Live with Larry · 18:10 · 548 views
LeetCode 815 Bus Routes | Minimum Buses Graph TraversalScott Hacks Code · 16:50 · 425 views
LEETCODE 815 BUS ROUTES PYTHONSasa codes · 14:15 · 425 views
The problem
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
- For example, if
routes[0] = [1, 5, 7], this means that the0thbus travels in the sequence1 -> 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 <= 105- All the values of
routes[i]are unique. sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106
Approach overview
Problem 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 1: Graph BFS Approach
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.
from collections import defaultdict, deque
def numBusesToDestination(routes, source, target):
if source == target:
return 0
stop_to_routes = defaultdict(set)
for i, route in enumerate(routes):
for stop in route:
stop_to_routes[stop].add(i)
queue = deque([(source, 0)]) # (current_stop, buses_taken)
visited_stops = {source}
visited_routes = set()
while queue:
stop, buses = queue.popleft()
for route in stop_to_routes[stop]:
if route in visited_routes:
continue
visited_routes.add(route)
for next_stop in routes[route]:
if next_stop == target:
return buses + 1
if next_stop not in visited_stops:
visited_stops.add(next_stop)
queue.append((next_stop, buses + 1))
return -1var numBusesToDestination = function(routes, source, target) {
if (source === target) return 0;
const stopToRoutes = new Map();
routes.forEach((route, i) => {
route.forEach(stop => {
if (!stopToRoutes.has(stop)) {
stopToRoutes.set(stop, new Set());
}
stopToRoutes.get(stop).add(i);
});
});
let queue = [[source, 0]];
const visitedStops = new Set([source]);
const visitedRoutes = new Set();
while (queue.length > 0) {
const [stop, buses] = queue.shift();
for (let route of stopToRoutes.get(stop) || []) {
if (visitedRoutes.has(route)) continue;
visitedRoutes.add(route);
for (let nextStop of routes[route]) {
if (nextStop === target) return buses + 1;
if (!visitedStops.has(nextStop)) {
visitedStops.add(nextStop);
queue.push([nextStop, buses + 1]);
}
}
}
}
return -1;
};This 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.
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.
Approach 2: Bidirectional BFS Approach
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.
import java.util.*;
class Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
Map<Integer, Set<Integer>> stopToRoute = new HashMap<>();
for (int i = 0; i < routes.length; i++) {
for (int stop : routes[i]) {
stopToRoute.computeIfAbsent(stop, k -> new HashSet<>()).add(i);
}
}
Set<Integer> visitedSource = new HashSet<>();
Set<Integer> visitedTarget = new HashSet<>();
Queue<int[]> queueSource = new LinkedList<>();
Queue<int[]> queueTarget = new LinkedList<>();
queueSource.offer(new int[]{source, 0});
visitedSource.add(source);
queueTarget.offer(new int[]{target, 0});
visitedTarget.add(target);
while (!queueSource.isEmpty() && !queueTarget.isEmpty()) {
int res = -1;
if (queueSource.size() <= queueTarget.size()) {
res = bfs(routes, stopToRoute, visitedSource, visitedTarget, queueSource);
} else {
res = bfs(routes, stopToRoute, visitedTarget, visitedSource, queueTarget);
}
if (res != -1) return res;
}
return -1;
}
private int bfs(int[][] routes, Map<Integer, Set<Integer>> stopToRoute,
Set<Integer> visitedThis, Set<Integer> visitedOther, Queue<int[]> queue) {
int count = queue.size();
while (count-- > 0) {
int[] current = queue.poll();
int stop = current[0];
int buses = current[1];
for (int route : stopToRoute.get(stop)) {
for (int nextStop : routes[route]) {
if (visitedOther.contains(nextStop)) return buses + 1;
if (visitedThis.add(nextStop)) {
queue.offer(new int[]{nextStop, buses + 1});
}
}
}
}
return -1;
}
}#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
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;
}
};This Java solution uses a bidirectional BFS approach to expedite the search process. By maintaining two BFS searches - one from the source and another from the target - and keeping track of visited stops using sets, the algorithm can detect an intersection far quicker, which represents a viable path from source to target. The method optimally chooses which search side to expand at each step based on queued elements, enhancing performance over standard BFS methods.
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 other auxiliary data structures.
Approach 3: BFS
First, we check if source and target are the same. If they are, we directly return 0.
Next, we use a hash table g to build a mapping from stops to bus routes. For each bus route, we traverse all the stops it passes through and map each stop to that bus route, i.e., g[stop] represents all bus routes passing through stop stop.
Then, we check if source and target are in the stop mapping. If they are not, we return -1.
We use a queue q to perform a breadth-first search (BFS). Each element in the queue is a tuple (stop, busCount), representing the current stop stop and the number of buses taken to reach the current stop busCount.
We initialize a set visBus to record the bus routes that have been visited and a set visStop to record the stops that have been visited. Then, we add source to visStop and (source, 0) to the queue q.
Next, we start the BFS. While the queue q is not empty, we take out the first element from the queue, which is the current stop stop and the number of buses taken to reach the current stop busCount.
If the current stop stop is the target stop target, we return the number of buses taken to reach the target stop busCount.
Otherwise, we traverse all bus routes passing through the current stop. For each bus route, we traverse all stops on that route. If a stop nextStop has not been visited, we add it to visStop and add (nextStop, busCount + 1) to the queue q.
Finally, if we cannot reach the target stop, we return -1.
The time complexity is O(L), and the space complexity is O(L), where L is the total number of stops on all bus routes.
function numBusesToDestination(routes: number[][], source: number, target: number): number {
if (source === target) {
return 0;
}
const g: Map<number, number[]> = new Map();
for (let i = 0; i < routes.length; i++) {
for (const stop of routes[i]) {
if (!g.has(stop)) {
g.set(stop, []);
}
g.get(stop)!.push(i);
}
}
if (!g.has(source) || !g.has(target)) {
return -1;
}
const q: [number, number][] = [[source, 0]];
const visBus: Set<number> = new Set();
const visStop: Set<number> = new Set([source]);
for (const [stop, busCount] of q) {
if (stop === target) {
return busCount;
}
for (const bus of g.get(stop)!) {
if (!visBus.has(bus)) {
visBus.add(bus);
for (const nextStop of routes[bus]) {
if (!visStop.has(nextStop)) {
visStop.add(nextStop);
q.push([nextStop, busCount + 1]);
}
}
}
}
}
return -1;
}public class Solution {
public int NumBusesToDestination(int[][] routes, int source, int target) {
if (source == target) {
return 0;
}
// Use Dictionary to map stops to bus routes
var g = new Dictionary<int, List<int>>();
for (int i = 0; i < routes.Length; i++) {
foreach (int stop in routes[i]) {
if (!g.ContainsKey(stop)) {
g[stop] = new List<int>();
}
g[stop].Add(i);
}
}
// If source or target is not in the mapping, return -1
if (!g.ContainsKey(source) || !g.ContainsKey(target)) {
return -1;
}
// Initialize queue and visited sets
var q = new Queue<int[]>();
var visBus = new HashSet<int>();
var visStop = new HashSet<int>();
q.Enqueue(new int[] { source, 0 });
visStop.Add(source);
// Begin BFS
while (q.Count > 0) {
var current = q.Dequeue();
int stop = current[0], busCount = current[1];
// If the current stop is the target stop, return the bus count
if (stop == target) {
return busCount;
}
// Traverse all bus routes passing through the current stop
foreach (int bus in g[stop]) {
if (visBus.Add(bus)) {
// Traverse all stops on this bus route
foreach (int nextStop in routes[bus]) {
if (visStop.Add(nextStop)) {
q.Enqueue(new int[] { nextStop, busCount + 1 });
}
}
}
}
}
return -1; // If unable to reach the target stop, return -1
}
}func numBusesToDestination(routes [][]int, source int, target int) int {
if source == target {
return 0
}
g := make(map[int][]int)
for i, route := range routes {
for _, stop := range route {
g[stop] = append(g[stop], i)
}
}
if g[source] == nil || g[target] == nil {
return -1
}
q := list.New()
q.PushBack([2]int{source, 0})
visBus := make(map[int]bool)
visStop := make(map[int]bool)
visStop[source] = true
for q.Len() > 0 {
front := q.Front()
q.Remove(front)
stop, busCount := front.Value.([2]int)[0], front.Value.([2]int)[1]
if stop == target {
return busCount
}
for _, bus := range g[stop] {
if !visBus[bus] {
visBus[bus] = true
for _, nextStop := range routes[bus] {
if !visStop[nextStop] {
visStop[nextStop] = true
q.PushBack([2]int{nextStop, busCount + 1})
}
}
}
}
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Graph BFS Approach | 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. |
| Bidirectional BFS Approach | 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. |
| BFS | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Bus Routes easy or hard?
Bus Routes is categorized as a hard problem because the main challenge is modeling the scenario as a graph of routes and stops. Once the graph representation is understood, applying BFS to compute the minimum number of buses becomes straightforward.
Bus Routes Python/Java solution
Most implementations build a stop-to-routes dictionary or map, then perform BFS using a queue. Python commonly uses defaultdict and deque, while Java solutions rely on HashMap and ArrayDeque for efficient traversal.
How to solve Bus Routes in O(n)?
Strict O(n) is not achievable because each route contains multiple stops. The optimal practical solution is O(N * K) using BFS with a stop-to-routes hash map. This allows constant-time lookups to find all routes connected to a given stop.
What is the best approach for Bus Routes?
The most effective approach models the problem as a graph and uses Breadth-First Search (BFS). Build a mapping from bus stop to all routes passing through that stop, then run BFS starting from routes containing the source stop. Each BFS level represents taking one more bus, guaranteeing the minimum number of transfers.
Is Bus Routes asked at Google/Amazon/Meta?
Bus Routes is a known hard graph traversal problem and has appeared in interview preparation lists for companies like Google, Amazon, and Meta. It tests graph modeling, BFS traversal, and efficient use of hash maps for adjacency lookup.
What data structure is used in Bus Routes?
The solution primarily uses a hash map to map stops to routes and a queue for BFS traversal. Arrays store the route definitions, while visited sets prevent revisiting routes or stops during the search.
What is the time complexity of Bus Routes?
The typical BFS solution runs in O(N * K) time where N is the number of routes and K is the average number of stops per route. Each route and stop is processed at most once while exploring neighboring routes through a stop-to-route hash map.