Bus Routes

A city runs several bus lines. routes[i] lists the stops served by bus i; each bus drives its stops in a loop forever, so from any stop on a line you can ride to any other stop on the same line.

You start at stop source (not yet on a bus) and want to get to stop target. You may only travel by bus, and you can switch buses at any stop that both lines serve.

Return the fewest number of buses you must board to reach target, or -1 if it cannot be reached. If source equals target, no bus is needed and the answer is 0.

Example 1

Example 2

Example 3

Constraints

• 1 <= routes.length <= 500
• 1 <= routes[i].length <= 105
• The stops within one route are distinct.
• The total number of stops over all routes is at most 105.
• 0 <= routes[i][j], source, target < 106

Pattern Path · Graphs: Traversal · problem 138 of 169

Start simple

Connect every pair of stops that share a bus and BFS over stops: a single route with L stops creates L² edges, so this is O(sum of L²) time and memory.

The key idea

Think of the trip as a sequence of buses. Once you are on a bus, every stop of that bus is reachable for the same price, so the real graph is which buses touch which stops, and each edge you pay for is "board one more bus". All costs are equal, so breadth-first search gives the minimum.

First build buses_at[stop], the list of buses serving each stop. Then BFS in rounds. The frontier starts as {source}. In each round, for every frontier stop, board each bus there that has not been boarded yet, and walk its whole route. Every stop you see for the first time joins the next frontier. If you see target during round r, the answer is r: BFS finds stops in order of how many buses they need, so no shorter way exists.

The key to speed is marking buses as used. A bus is expanded at most once, so each route list is scanned once, and the total work is proportional to the total number of stops in the input. Avoid building stop-to-stop edges: one long route would create a quadratic number of them.

Complexity

• Time: O(S), where S is the total number of stops over all routes
• Space: O(S)

Python

class Solution:
    def numBusesToDestination(self, routes, source, target):
        if source == target:
            return 0

        # For every stop, remember which buses pass through it.
        buses_at = defaultdict(list)
        for bus, route in enumerate(routes):
            for stop in route:
                buses_at[stop].append(bus)

        # BFS in rounds: round r reaches every stop that needs exactly r buses.
        boarded = [False] * len(routes)
        reached = {source}
        frontier = [source]
        rides = 0
        while frontier:
            rides += 1
            next_frontier = []
            for stop in frontier:
                for bus in buses_at[stop]:
                    if boarded[bus]:
                        continue
                    boarded[bus] = True  # each bus is expanded only once
                    for nxt in routes[bus]:
                        if nxt == target:
                            return rides
                        if nxt not in reached:
                            reached.add(nxt)
                            next_frontier.append(nxt)
            frontier = next_frontier
        return -1

JavaScript

var numBusesToDestination = function(routes, source, target) {
  if (source === target) return 0;

  // For every stop, remember which buses pass through it.
  const busesAt = new Map();
  routes.forEach((route, bus) => {
    for (const stop of route) {
      if (!busesAt.has(stop)) busesAt.set(stop, []);
      busesAt.get(stop).push(bus);
    }
  });

  // BFS in rounds: round r reaches every stop that needs exactly r buses.
  const boarded = new Array(routes.length).fill(false);
  const reached = new Set([source]);
  let frontier = [source];
  let rides = 0;
  while (frontier.length > 0) {
    rides++;
    const nextFrontier = [];
    for (const stop of frontier) {
      for (const bus of busesAt.get(stop) || []) {
        if (boarded[bus]) continue;
        boarded[bus] = true; // each bus is expanded only once
        for (const nxt of routes[bus]) {
          if (nxt === target) return rides;
          if (!reached.has(nxt)) {
            reached.add(nxt);
            nextFrontier.push(nxt);
          }
        }
      }
    }
    frontier = nextFrontier;
  }
  return -1;
};

What the interviewer is checking

The interviewer wants to see you pick the right graph to search. Modelling buses (not stops) as the unit of cost, and noticing that BFS gives the minimum, is the whole problem.

Mistakes to avoid

• Forgetting the source == target case, which must return 0 even if that stop is on no route.
• Building edges between every pair of stops on a route, which blows up to quadratic size on long routes.
• Re-scanning a bus's route every time one of its stops is reached instead of marking the bus as used.
• Counting stops travelled instead of buses boarded.

Follow-ups to expect

• What if each ride also had a fare and you wanted the cheapest trip? (Dijkstra over buses with weights.)
• How would you return the actual list of buses taken? (Store parent bus per stop.)
• Could you search from both ends at once? (Bidirectional BFS meeting in the middle.)

In real software

Journey planners for public transport minimise the number of transfers in the same way, searching over lines rather than individual stops before refining by time.

Practice next