Bus Routes
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber 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.
Visual walkthrough for routes = [[1, 2, 7], [3, 6, 7]], source 1, target 6:
- index: 1->[0], 2->[0], 7->[0,1], 3->[1], 6->[1]
- level 0 (buses 0): queue = [1]
- level 1 (buses 1): pop 1 -> board route 0 -> stops 1, 2, 7; target 6 not hit; enqueue 2, 7.
- level 2 (buses 2): pop 2 (route 0 boarded, skip), pop 7 -> board route 1 -> stops 3, 6, 7; hit 6. Answer 2.
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.
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Bus Routes?
Bus Routes is asked at Uber. 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.