815. Bus Routes
Asked at Uber, Pinterest
Difficulty
Hard
Time
O(n + m)
Space
O(n + m)
Pattern
Array
Companies
2
Problem
You are given a list of bus routes. Each routes[i] is one bus line: that bus drives through those stops in order and then loops back to the start, forever. So a bus on route [1, 5, 7] keeps visiting 1, 5, 7, 1, 5, 7, ... with no end.
You begin standing at the stop source and you are not on any bus. You want to reach the stop target. You may only move by riding buses, and you can get off at any stop a bus visits. Each time you step onto a bus counts as one bus taken, no matter how many stops you ride.
Return the smallest number of buses you must take to get from source to target. If it is impossible, return -1. If source equals target, the answer is 0 — you are already there and never board anything.
Two routes that share one stop
Constraints
- ●
1 <= routes.length <= 500 - ●
1 <= routes[i].length <= 10^5 - ●
All the values of routes[i] are unique - ●
sum(routes[i].length) <= 10^5 - ●
0 <= routes[i][j] < 10^6 - ●
0 <= source, target < 10^6
Examples
routes = [[1,2,7],[3,6,7]], source = 1, target = 62routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12-1Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
| Hard | View all Pinterest questions → |
How to Think About It
Baseline: treat every stop as a node and connect all stops that share a route. Building such an adjacency list is O(k²) per route (every pair of stops), which explodes because stop counts reach 10^5.
Key insight: count buses, not stops. Boarding a bus cost one unit and then covers every stop on that route, so BFS should expand stop -> routes serving it -> stops on those routes, tracking how many routes have been boarded.
Build a reverse index: a hash map from each stop to the list of route indices that serve it. BFS starts at the source stop and, for each stop, enters every route not yet boarded, then fans out to all stops of those routes.
Why skipping boarded routes is correct: once a route is taken, every stop on it is reachable at the current bus count. Re-boarding the same route later cannot lower the answer, so each route expands at most once - O(n + m) total work.
Edge cases: source equals target returns 0 even when no route serves either stop; routes that loop revisit their own stops, so a visited-stops set prevents infinite expansion.
Optimal Approach
Model the problem as BFS where traversing to a new bus is exactly one level. Precompute a mapping from each stop to the list of route indices that include it. Seed a queue with the source stop. For each level, take all stops at the current depth; for each, board every route that was not boarded before, and from those routes enqueue every stop not yet visited. The first time the target is produced, return the current depth; if the queue empties first, return -1.
Walkthrough for routes = [[1, 2, 7], [3, 6, 7]], source 1, target 6:
- Level 0: queue = [1].
- Level 1: pop 1, board route 0 (stop 1, 2, 7). Target 6 not hit; enqueue 2, 7.
- Level 2: pop 2 (route 0 already boarded, skip). Pop 7, board route 1 (stops 3, 6, 7). Target 6 found. Return 2.
Time: O(n + m) where n is the number of routes and m the total number of stops; space: O(n + m) for the index and sets.
BFS over buses, not stops
What Trips People Up in Real Interviews
Building a full stop-to-stop graph. Interconnecting every pair on a route is O(k²) memory and does not scale. Index stops to routes and expand through the route lists instead.
Forgetting the source equals target case. The answer is 0 buses - return it before touching the graph, or you can wrongly return -1 when no route serves either stop.
Counting stops instead of buses. Each BFS level must represent exactly one newly boarded bus. Riding a route to all its stops must happen inside a single level; incrementing per stop over-counts.
Re-solving the same route from every one of its stops. Without a visited-routes set, the same bus is boarded repeatedly and the search explodes to quadratic work. Track boarded routes globally, not per path.
Checking the target in the wrong scope. The target must be detected while expanding a newly boarded route, or the level-to-bus mapping drifts by one and the returned minimum is wrong.
Solution Code
O(n + m) timefrom collections import defaultdict, deque
def numBusesToDestination(routes, source, target):
if source == target:
return 0
stop_to_routes = defaultdict(list)
for i, route in enumerate(routes):
for stop in route:
stop_to_routes[stop].append(i)
q = deque([source])
visited_stops = {source}
visited_routes = set()
buses = 0
while q:
buses += 1
size = len(q)
for _ in range(size):
stop = q.popleft()
for route_idx in stop_to_routes[stop]:
if route_idx in visited_routes:
continue
visited_routes.add(route_idx)
for next_stop in routes[route_idx]:
if next_stop == target:
return buses
if next_stop not in visited_stops:
visited_stops.add(next_stop)
q.append(next_stop)
return -1Frequently Asked Questions
What is the Bus Routes problem?
You are given a list of bus routes, each a sequence of stops that bus visits on a loop. Find the minimum number of buses required to travel from a source stop to a target stop, or -1 if impossible - the Uber BFS problem that asks you to reason about graph modeling.
How do you solve Bus Routes?
The optimal approach runs in O(n + m) time and O(n + m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Bus Routes?
Bus Routes is asked at Uber, Pinterest. It is a hard difficulty problem.
What are common mistakes on Bus Routes?
- Building a full stop-to-stop graph. Interconnecting every pair on a route is `O(k²)` memory and does not scale. Index stops to routes and expand through the route lists instead.
- Forgetting the source equals target case. The answer is 0 buses - return it before touching the graph, or you can wrongly return -1 when no route serves either stop.
- Counting stops instead of buses. Each BFS level must represent exactly one newly boarded bus. Riding a route to all its stops must happen inside a single level; incrementing per stop over-counts.
- Re-solving the same route from every one of its stops. Without a visited-routes set, the same bus is boarded repeatedly and the search explodes to quadratic work. Track boarded routes globally, not per path.
- Checking the target in the wrong scope. The target must be detected while expanding a newly boarded route, or the level-to-bus mapping drifts by one and the returned minimum is wrong.