Frequently Asked at Uber — This problem has been reported multiple times in recent Uber L5A interviews.

Bus Routes

Problem Statement

You are given routes, where routes[i] is the list of bus stops that bus i cycles through. You can ride any bus any number of times, but each bus ride costs one bus. Starting at stop source, return the minimum number of buses you must take to reach target. Return -1 if impossible.

Example 1:

Input: routes = [[1, 2, 7], [3, 6, 7]], source = 1, target = 6
Output: 2
Explanation: Take bus 0 from stop 1 to stop 7, then bus 1 from stop 7 to 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 <= 10^5
• Total stops across all routes up to 10^5.

Difficulty: Hard

---

Pattern Recognition

• What is the structure of the input? A bipartite-style relation between stops and buses.
• What are we optimizing? Minimum number of buses (edges in the "bus" graph) from source to target.
• What pattern does this suggest? Breadth-first search on the bus graph, not the stop graph.
• Why does this pattern fit? Each bus ride adds exactly 1 to the answer, and unit-weight shortest paths are what BFS solves. The trick is choosing the right graph: buses as nodes, shared stops as edges, gives you a much smaller and cleaner search space than stops as nodes.

---

Approach

Brute Force — DFS with all routes

Enumerate every possible sequence of buses. You quickly hit exponential blowup because cycles of "take bus A, take bus B, take bus A again" are everywhere.

Time: Exponential. Space: Exponential. Why insufficient: Will TLE even on moderate inputs.

Optimal — Multi-source BFS on buses

Key Insight: Don't BFS on stops. Each bus hop moves you between buses that share at least one stop, and BFS-distance on that bus graph is exactly the minimum number of buses taken.

Step-by-step:

1. Build a map stopToBuses: stop -> list of buses by scanning every route.
2. Start BFS from source. At each level, for every unvisited bus that stops at the current stop, mark the bus visited and enqueue every stop on that bus with distance count + 1.
3. Also track visited stops so you don't revisit.
4. Return count + 1 the first time you step onto target. Return -1 if the BFS drains with no hit.

Time: O(N * M) where N = number of buses, M = total stops. Space: O(N * M) for the map and visited sets.

---

Walkthrough

Using routes = [[1,2,7], [3,6,7]], source=1, target=6.

Build stopToBuses:

Stop	Buses
1	[0]
2	[0]
7	[0, 1]
3	[1]
6	[1]

BFS trace:

Step	Queue before pop	Stop popped	Count	Visit buses	Observe
1	[(1, 0)]	1	0	bus 0	Push 2, 7 with count 1
2	[(2,1), (7,1)]	2	1	bus 0 already visited	—
3	[(7,1)]	7	1	bus 1	Push 3, 6 — 6 is the target! Return 1+1=2

Answer: 2.

---

Implementation

TypeScript

function numBusesToDestination(routes: number[][], source: number, target: number): number {
  if (source === target) return 0;
  const stopToBuses = new Map<number, number[]>();
  for (let bus = 0; bus < routes.length; bus++) {
    for (const stop of routes[bus]) {
      if (!stopToBuses.has(stop)) stopToBuses.set(stop, []);
      stopToBuses.get(stop)!.push(bus);
    }
  }

  const visitedBuses = new Set<number>();
  const visitedStops = new Set<number>([source]);
  const queue: Array<[number, number]> = [];
  queue.push([source, 0]);

  while (queue.length > 0) {
    const [stop, count] = queue.shift()!;
    const buses = stopToBuses.get(stop) ?? [];
    for (const bus of buses) {
      if (visitedBuses.has(bus)) continue;
      visitedBuses.add(bus);
      for (const nextStop of routes[bus]) {
        if (nextStop === target) return count + 1;
        if (!visitedStops.has(nextStop)) {
          visitedStops.add(nextStop);
          queue.push([nextStop, count + 1]);
        }
      }
    }
  }
  return -1;
}

C++

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;
        unordered_map<int, vector<int>> stopToBuses;
        for (int bus = 0; bus < (int)routes.size(); ++bus)
            for (int stop : routes[bus])
                stopToBuses[stop].push_back(bus);

        unordered_set<int> visitedBuses, visitedStops{source};
        queue<pair<int,int>> q;
        q.push({source, 0});

        while (!q.empty()) {
            auto [stop, count] = q.front(); q.pop();
            for (int bus : stopToBuses[stop]) {
                if (visitedBuses.count(bus)) continue;
                visitedBuses.insert(bus);
                for (int next : routes[bus]) {
                    if (next == target) return count + 1;
                    if (!visitedStops.count(next)) {
                        visitedStops.insert(next);
                        q.push({next, count + 1});
                    }
                }
            }
        }
        return -1;
    }
};

Watch out: The source == target shortcut. If you forget it you return 1 when the right answer is 0.

Watch out: Marking buses visited (not just stops). Without visitedBuses, you pay the full O(stops-on-bus) work every time you re-enter the same bus.

Watch out: BFS on stops without the bus map — a straightforward adjacency-list BFS over stops gives you the wrong metric (you would count stops, not buses).

---

Complexity Analysis

	Time	Space
Brute Force (enumerate sequences)	Exponential	Exponential
Optimal (multi-source BFS)	O(N * M)	O(N * M)

Bottleneck: In the worst case, you visit every (bus, stop) pair once while building the map and once again during BFS. Both are O(N*M).

---

Edge Cases

1. source == target — Return 0 immediately.
2. source appears on no bus — BFS finds no neighbors; return -1.
3. target is unreachable — BFS drains; return -1.
4. Multiple buses share every stop — Your visitedBuses set prevents redundant work.
5. One very long route — O(M) for that bus's inner loop is unavoidable, but we only pay it once.

---

Related Problems

• LC 127 — Word Ladder: BFS on a transformed graph, same "redefine the node" insight.
• LC 1293 — Shortest Path in a Grid with Obstacles Elimination: BFS with augmented state.
• LC 2290 — Minimum Obstacle Removal to Reach Corner: Shortest path on a grid with weighted edges.
• LC 1091 — Shortest Path in Binary Matrix: Plain BFS for minimum steps.

---

What Is Expected at Each Level?

Junior / New Grad: Recognize BFS for shortest path in an unweighted graph. May instinctively model stops as nodes and need a nudge to see that BFS-on-buses is cleaner.

Mid-level: Immediately build the stopToBuses map and BFS on it. Explain why BFS gives the minimum number of buses and not stops. Handle edge cases cleanly.

Senior: Discuss when to BFS on stops vs buses (sparse stops / dense routes vs the opposite). Propose variants: weighted buses (Dijkstra), time-dependent schedules (time-expanded graph), returning the actual itinerary by tracking parent pointers.