Bus Routes — BFS over Routes Instead of Stops for Minimum Transfers

Problem Statement#

You are given an array routes where routes[i] is the ordered list of stops served by bus i. Each bus runs in a circular loop forever, so once you board a bus you can ride it to any stop in routes[i]. You start at the stop source and want to reach the stop target. Return the minimum number of buses you must take. If it is impossible, return -1. If source equals target, the answer is zero buses.

This is a shortest-path problem on an implicit graph, but the metric being minimized is bus boardings, not stop hops.

Why This Problem Matters#

Bus Routes is a transit-themed shortest-path question that comes up at Uber, Lyft, Amazon, and Google. It is a stress test for BFS modeling: candidates who default to BFS over stops produce a correct but exponentially slow solution because each step expands every neighbor stop, but each stop can belong to many buses, and you double-count work massively. The optimal version reframes the graph so that BFS levels count bus boardings, which directly matches what the problem asks for.

The reframing is the lesson interviewers care about. They want to see whether you choose the right state space and the right edges before you write any code. This skill transfers to nearly every transit, network-routing, and game-search problem you will encounter.

The Core Insight#

Think of buses, not stops, as the BFS frontier. Two key observations drive the solution. First, once you board a bus, riding it to any of its stops is free in terms of boardings, so the cost of boarding bus i is one regardless of which of its stops you alight at. Second, you can transfer between buses only at shared stops, so two buses are neighbors in the route graph if and only if they share at least one stop.

You build a stop_to_routes index that maps each stop to the set of bus indices serving it. BFS starts from every bus that contains source, and each BFS step iterates over all unvisited buses sharing a stop with the current bus. The number of BFS levels traversed when you finally reach a bus that contains target equals the minimum number of boardings.

A common variant runs BFS over stops but increments the boarding count when you traverse all stops of a bus, marking the bus visited so you do not revisit it. Both formulations have the same complexity; the route-graph formulation is a touch cleaner conceptually.

Visual Dry Run (BFS/DFS trace)#

Take routes equal to [[1, 2, 7], [3, 6, 7]], source equal to 1, target equal to 6.

Stop-to-routes index. Stop 1 maps to set with route 0. Stop 2 maps to set with route 0. Stop 7 maps to set with routes 0 and 1. Stop 3 maps to set with route 1. Stop 6 maps to set with route 1.

BFS init. Source equals 1, target equals 6. Mark visited stop 1. Push the tuple containing stop 1 and 0 buses onto the queue.

Iteration one. Pop stop 1 with 0 buses. Stop 1 belongs to route 0. Mark route 0 visited. Iterate the stops of route 0. Stop 1 equals source already. Stop 2 not target, mark visited, push with 1 bus. Stop 7 not target, mark visited, push with 1 bus.

Iteration two. Pop stop 2 with 1 bus. Stop 2 belongs to route 0, already visited.

Iteration three. Pop stop 7 with 1 bus. Stop 7 belongs to routes 0 (visited) and 1. Mark route 1 visited. Iterate stops of route 1. Stop 3 not target, push with 2 buses. Stop 6 equals target, return 2 buses.

The bug-free answer is 2: take route 0 from stop 1 to stop 7, transfer to route 1, ride to stop 6.

Solution (Optimal)#

Python — BFS over routes via stop index#

from collections import deque, defaultdict
 
class Solution:
    def numBusesToDestination(self, routes, source, target):
        if source == target:
            return 0
        stop_to_routes = defaultdict(set)
        for i, route in enumerate(routes):
            for stop in route:
                stop_to_routes[stop].add(i)
        visited_stops = {source}
        visited_routes = set()
        q = deque([(source, 0)])
        while q:
            stop, buses = q.popleft()
            for route_id in stop_to_routes[stop]:
                if route_id in visited_routes:
                    continue
                visited_routes.add(route_id)
                for s in routes[route_id]:
                    if s == target:
                        return buses + 1
                    if s not in visited_stops:
                        visited_stops.add(s)
                        q.append((s, buses + 1))
        return -1

JavaScript#

var numBusesToDestination = function(routes, source, target) {
    if (source === target) return 0;
    const stopToRoutes = new Map();
    routes.forEach((route, i) => {
        for (const s of route) {
            if (!stopToRoutes.has(s)) stopToRoutes.set(s, []);
            stopToRoutes.get(s).push(i);
        }
    });
    const visitedStops = new Set([source]);
    const visitedRoutes = new Set();
    const q = [[source, 0]];
    while (q.length) {
        const [stop, buses] = q.shift();
        for (const r of stopToRoutes.get(stop) || []) {
            if (visitedRoutes.has(r)) continue;
            visitedRoutes.add(r);
            for (const s of routes[r]) {
                if (s === target) return buses + 1;
                if (!visitedStops.has(s)) {
                    visitedStops.add(s);
                    q.push([s, buses + 1]);
                }
            }
        }
    }
    return -1;
};

Time complexity is O(R times K plus E) where R is the number of routes, K is the average stops per route, and E is the total transfers between routes. Space complexity is O(R times K) for the inverted index plus visited sets.

Common Mistakes#

BFS over stops without marking entire routes visited blows up in time because each stop revisits every bus through it. Forgetting to handle source equal to target returns 1 instead of 0. Using a list as the inner container of stop_to_routes and not deduplicating allows the same route to be processed multiple times. Increasing the boarding counter when moving stops along the same route is wrong; the cost is per route boarded. Returning -1 inside the loop when the queue empties early misses valid paths that visit through different transfers; only return -1 after the loop.

Interview Tips#

State the modeling decision first: BFS levels are buses, not stops. Sketch the stop-to-routes inverted index and explain how it lets you find connected routes in constant time per stop. Mention the alternative formulation where the graph is directly route-to-route (build edges between routes that share any stop) and contrast the precompute cost. Walk through the source-equals-target edge case and the unreachable case. If pressed for further optimization, mention bidirectional BFS from source and target route sets, which often halves the work on dense networks.

Follow-up Questions#

What if some buses run only at certain times? Then edges become time-dependent and you need a Dijkstra over a (route, time) state. What if you also want to minimize total stops traveled, not just transfers? Use a multi-objective Dijkstra with a tuple key (boardings, stops). How would you reconstruct the actual route? Track parent route pointers during BFS and walk back from the bus that hit the target. What if route lists are streamed and updates arrive frequently? Maintain the inverted index incrementally; route graphs reflect updates without rebuilding from scratch.

Key Takeaways#

• Bus Routes minimizes bus boardings, so BFS levels must count routes, not stops
• Build a stop-to-routes inverted index in O(total stops) time
• Mark routes visited the first time you process them so you never re-expand a bus
• BFS terminates as soon as a route in the frontier contains the target stop
• Handle source equal to target upfront to avoid returning 1
• The same modeling pattern beats Open the Lock, Word Ladder, and any transfer-minimization graph