Bus Routes
Find the fewest buses between two stops with a BFS whose levels count rides, not stops.
Examples
Bus 0 from stop 1 to stop 7, then bus 1 from stop 7 to stop 6.
The buses through stop 15 reach 4, 5 and 19 only — never one that serves 12.
Problem Understanding
routes[i] is the list of stops that bus i drives round, in a loop, for ever. You start at stop source, you want to reach stop target, and you may change buses at any stop two routes share (LeetCode 815).
- Input:
routes = [[1,2,7],[3,6,7]],source = 1,target = 6. - Output:
2— bus 0 from stop 1 to stop 7, change there, then bus 1 from stop 7 to stop 6. - Goal: the fewest buses, not the fewest stops. Riding one bus past twenty stops still costs 1.
When no chain of transfers reaches the target, return -1.
Algorithm Strategy
Fewest buses is a shortest-path question where every ride costs 1, so it is BFS. The difficulty is choosing what the nodes are.
Why not stop to stop. Joining every pair of stops on a route builds a clique: a route with 10^5 stops would need about 5 × 10^9 edges. The thing to walk is the route, not the pairs.
- Index the routes: one pass over every stop of every route builds
stop → the buses that serve it. - Queue stops, count buses: the queue holds stops, and each pass of the outer loop is one more bus taken — so every stop dequeued during that pass costs the same number of rides.
- Ride each bus once: for the stop at the front of the queue, look at the buses serving it. One already ridden is skipped, because everything it reaches is already known. A new one is marked ridden, and every stop on its route is examined.
- Stop at the target: the first ride that reaches the target ends the search, and the current count is the answer.
- Empty queue: no chain of transfers gets there, so return -1.
The two visited sets do different jobs. The bus set is what keeps the work linear — a route is walked at most once in the whole search. The stop set only keeps the queue from holding the same stop twice.
Interactive Visualization
The ring on the left is the stops and the column on the right is the buses, with a line wherever a bus serves a stop — which is exactly the index the code builds in step 1. Riding a bus lights the line into it, then the line out to each stop on its route. The number above a stop is the value of buses when that stop joined the queue, so the moment the target lights up, the answer is already written above it.
Dry Run
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6.
The index built first: 1 → bus 0, 2 → bus 0, 7 → bus 0 and bus 1, 3 → bus 1, 6 → bus 1.
buses |
Stop dequeued | Buses serving it | Ridden now | Stops on that route | Queue after |
|---|---|---|---|---|---|
| 1 | 1 | bus 0 | bus 0 | 1 is already known; 2 and 7 are new | [2, 7] |
| 2 | 2 | bus 0 | none — bus 0 has been ridden | — | [7] |
| 2 | 7 | bus 0, bus 1 | bus 1 (bus 0 skipped) | 3 is new, then 6 is the target | — |
Bus 1 reaches stop 6 while buses is 2, so the answer is 2. Stop 2 cost a dequeue and produced nothing, which is normal: the stop is reachable, but the only bus through it had already been ridden.
Edge Cases & Common Mistakes
Edge Cases:
source == target: return 0 before anything is built.- Unreachable target: the queue empties and the answer is -1.
- A target no route serves: the same -1 — no ride can reach it.
- Size: up to 10^5 stops across all routes, which is why riding each route at most once matters.
Common Mistakes:
- Building a stop-to-stop graph, which is the clique that times out.
- Forgetting to mark a route as ridden, so its stops are walked again for every stop on it.
- Counting stops instead of buses: the counter goes up once per level, which is once per ride.
- Checking for the target only as a stop is dequeued, which costs an extra ride on the answer.
Solution Code
Index the stops once, then run a BFS over stops whose levels count bus rides (LeetCode 815).
Bus Routes Code
1var numBusesToDestination = function(routes, source, target) {2 if (source === target) {3 return 0;4 }5 const stopToBuses = new Map();6 for (let bus = 0; bus < routes.length; bus++) {7 for (const stop of routes[bus]) {8 if (!stopToBuses.has(stop)) {9 stopToBuses.set(stop, []);10 }11 stopToBuses.get(stop).push(bus);12 }13 }14 const queue = [source];15 let head = 0;16 const visitedStops = new Set([source]);17 const ridden = new Set();18 let buses = 0;19 while (head < queue.length) {20 buses++;21 const size = queue.length - head;22 for (let i = 0; i < size; i++) {23 const stop = queue[head++];24 for (const bus of stopToBuses.get(stop) || []) {25 if (ridden.has(bus)) {26 continue;27 }28 ridden.add(bus);29 for (const nextStop of routes[bus]) {30 if (nextStop === target) {31 return buses;32 }33 if (visitedStops.has(nextStop)) {34 continue;35 }36 visitedStops.add(nextStop);37 queue.push(nextStop);38 }39 }40 }41 }42 return -1;43};