Coding · Graphs and grids
Bus Routes
- Appears on company lists
- Hard
- 2 sources
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
Each bus follows a route, a list of stops it visits in a loop forever. You start at one stop and want to reach another using as few different buses as possible, changing buses at any stop shared by two routes. Return the minimum number of buses, or -1 if the target cannot be reached. For routes [[1,2,7],[3,6,7]], start 1 and target 6, the answer is 2: ride the first bus to stop 7, then the second bus to stop 6. Assume up to 500 routes, 100,000 stop entries in total, and stop numbers below one million.
Restated in our own words, not a quote from Uber or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: what exactly is the cost, the number of buses or the number of stops passed? (Buses.) Can a stop appear twice in one route? Can the start equal the target, and what is the answer then? Can a route list be empty, or can the list of routes be empty? How large can a single route be compared with the number of routes?
I would assume the cost is the number of different buses boarded, that the start equal to the target needs zero buses, that unreachable means -1, and that stop numbers are sparse so I should key everything by stop number in a Map, not an array.
Brute force
Say the obvious answer and why it is too slow.
The obvious model is a graph of stops, with an edge between any two stops that share a route, then a breadth-first search from the start. It has two problems. First, a route with L stops becomes a clique of about L² / 2 edges, so one route of 100,000 stops needs around five billion edges. Second, if you avoid that blow-up by linking only consecutive stops, an edge counts one hop, but riding past fifty stops on one bus costs one bus, so plain hop counting gives the wrong answer.
Rescanning every route for every stop is also slow: O(stops · total entries). We need a model where the cost of one unit equals one bus.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(S²)
- Time
- O(S)
- Space
- O(S)
The pattern is BFS over routes, not over stops. Make each route a node. Two routes are neighbours if they share a stop. Boarding a route costs one bus, and every stop on it is then free, so the answer is the shortest path measured in routes.
First build a Map from stop to the list of routes that pass through it. That lookup turns "which other buses can I change to here?" into one step. Layer 1 is the set of routes through the start stop. For each route in the current layer, walk its stops: if the stop is the target, the answer is the current layer number. Otherwise every route through that stop that we have not seen joins the next layer.
It is correct because BFS visits routes in order of the number of buses needed. The first time any route in layer d contains the target, no shorter option exists, since all routes in earlier layers were already scanned without finding it.
Two visited sets keep the work linear. A route is marked seen when it is queued, so it is never queued twice. A stop is marked seen the first time it is expanded, so its list of routes is walked only once. Then every stop entry is touched a bounded number of times and the total work is proportional to the number of stop entries, not to the number of routes squared. The start equal to the target is a special case worth saying first: zero buses, even if no route exists.
Walk it through
A dry run on the example, step by step.
| step | buses | route | stop scanned | what happens |
|---|---|---|---|---|
| 0 | 0 | - | index built | stop 7 is on routes 0, 1 |
| 1 | 1 | route 0 | 1 | route 0 only, seen |
| 2 | 1 | route 0 | 2 | route 0 only, seen |
| 3 | 1 | route 0 | 7 | route 1 is new, queued |
| 4 | 2 | route 1 | 3 | nothing new |
| 5 | 2 | route 1 | 6 | target found: answer 2 |
Build the index first: stop 7 appears on routes 0 and 1, every other stop on exactly one route. The start stop 1 is on route 0 only, so layer 1 is route 0 and the bus count is 1.
Walk route 0. Stops 1 and 2 only belong to route 0, which is already seen, so nothing is added. Stop 7 belongs to route 1, which is new, so route 1 joins the next layer. The bus count becomes 2 and we walk route 1: stop 3 adds nothing, and stop 6 is the target, so the function returns 2. The trace lists each scanned stop.
The code
Runnable JavaScript, checked against test cases.
function numBusesToDestination(routes, source, target) {
if (source === target) return 0;
const routesAtStop = new Map();
routes.forEach((stops, route) => {
for (const stop of stops) {
if (!routesAtStop.has(stop)) routesAtStop.set(stop, []);
routesAtStop.get(stop).push(route);
}
});
const seenRoutes = new Set();
const seenStops = new Set();
let frontier = [];
for (const route of routesAtStop.get(source) || []) {
if (!seenRoutes.has(route)) {
seenRoutes.add(route);
frontier.push(route);
}
}
for (let buses = 1; frontier.length > 0; buses++) {
const nextFrontier = [];
for (const route of frontier) {
for (const stop of routes[route]) {
if (stop === target) return buses;
if (seenStops.has(stop)) continue;
seenStops.add(stop);
for (const other of routesAtStop.get(stop)) {
if (!seenRoutes.has(other)) {
seenRoutes.add(other);
nextFrontier.push(other);
}
}
}
}
frontier = nextFrontier;
}
return -1;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Start equals target: return 0 before building anything, even when the list of routes is empty.
- Start on no route: the first layer is empty, the loop does not run, and the result is -1.
- Target on no route: the BFS exhausts every reachable route without a match and returns -1.
- Target on a route through the start: found in layer 1, answer 1.
- Repeated stop inside one route: the seen sets absorb it, with no double work.
- Many routes sharing the same stops: seen routes and seen stops stop the queue from growing past the number of routes.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the actual sequence of routes and transfer stops, not just the count?
- How would the answer change if each transfer also cost waiting time and each route had a different ticket price?
- Could a bidirectional search from the start and the target help, and when?
- What if stops are added to routes over time and you must answer many queries?
Where candidates slip
The mistakes this problem punishes.
Common mistakes:
- Running BFS over stops and counting stops, which charges for every stop instead of every bus.
- Building stop-to-stop edges for each route, which blows up memory on a long route.
- Forgetting a seen set for routes, which loops forever or repeats work.
- Marking a route as seen when it is dequeued rather than when it is queued, which lets duplicates in.
- Returning 1 or -1 when the start equals the target instead of 0.
- Searching the routes with includes for each stop, which makes the index step quadratic.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.