Bus Routes

HardGraph BFS · Hash Map Index🧩 Graph BFS LeetCode #815 ↗Updated Oct 30, 2026

Problem

Each routes[i] lists the stops a bus loops through forever. You stand at stop source and want to reach stop target, moving only by bus. Return the fewest buses you must board, or -1 if the target is unreachable. Staying at source when it equals target costs 0 buses.

Inputroutes = [[1,2,7],[3,6,7]], source = 1, target = 6Output2

Inputroutes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12Output-1

Inputroutes = [[1,2,3]], source = 2, target = 2Output0

1 ≤ routes.length ≤ 500 · 1 ≤ routes[i].length ≤ 10⁵ · stops within one route are distinct · ∑ routes[i].length ≤ 10⁵ · 0 ≤ stops, source, target < 10⁶

Try it yourself

Java

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

We count buses, not stops, so a BFS level is “one more bus”. Index stop → routes, and once a route has been boarded never scan it again — every stop on it is already reachable at that bus count.

PatternGraph BFS

Instinct Minimum moves, fewest steps or shortest transformation where every step costs the same: spread outward level by level with a queue.

Memory hack Ripples in a pond: every ring is one step farther, so the first ring that touches the target is the answer.

Open the Graph BFS guide →

Approaches

Brute ForceRoute Graph via Pairwise Intersection

Time O(R²·L)Space O(R² + ∑L)

Make each route a node and connect two routes if they share any stop (test every pair with a hash set). BFS from all routes containing source with distance 1; the first popped route containing target gives the answer. L is the longest route.

Java

public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) return 0;
    int r = routes.length;
    List<Set<Integer>> stops = new ArrayList<>();
    for (int[] route : routes) {
        Set<Integer> s = new HashSet<>();
        for (int x : route) s.add(x);
        stops.add(s);
    }
    // two routes are linked if they share at least one stop
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < r; i++) adj.add(new ArrayList<>());
    for (int i = 0; i < r; i++) {
        for (int j = i + 1; j < r; j++) {
            for (int x : routes[i]) {
                if (stops.get(j).contains(x)) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                    break;
                }
            }
        }
    }
    int[] dist = new int[r];
    Arrays.fill(dist, -1);
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < r; i++) {
        if (stops.get(i).contains(source)) {
            dist[i] = 1;
            queue.offer(i);
        }
    }
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        if (stops.get(cur).contains(target)) return dist[cur];
        for (int nxt : adj.get(cur)) {
            if (dist[nxt] == -1) {
                dist[nxt] = dist[cur] + 1;
                queue.offer(nxt);
            }
        }
    }
    return -1;
}

Correct and intuitive, but the all-pairs intersection step is quadratic in routes.

BetterStop-Level BFS with a Stop → Routes Index

Time O(∑L_i²)Space O(∑L)

Build a map from each stop to the routes serving it, then BFS over stops one bus count at a time: from a stop, ride every route through it and enqueue all unseen stops. Each stop is expanded once, but a route is rescanned once for every stop on it.

Java

public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) return 0;
    Map<Integer, List<Integer>> routesAt = new HashMap<>();
    for (int i = 0; i < routes.length; i++) {
        for (int stop : routes[i]) {
            routesAt.computeIfAbsent(stop, x -> new ArrayList<>()).add(i);
        }
    }
    Set<Integer> seen = new HashSet<>();
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(source);
    seen.add(source);
    int buses = 0;
    while (!queue.isEmpty()) {
        buses++;
        for (int size = queue.size(); size > 0; size--) {
            int stop = queue.poll();
            for (int bus : routesAt.getOrDefault(stop, List.of())) {
                for (int next : routes[bus]) {   // same route may be scanned again later
                    if (next == target) return buses;
                    if (seen.add(next)) queue.offer(next);
                }
            }
        }
    }
    return -1;
}

No pairwise step, yet long routes shared by many dequeued stops are rescanned.

OptimalStop-Level BFS + Boarded-Route Marking

Time O(∑L)Space O(∑L)

Same BFS, plus a boarded[] flag per route. The first time a route is reached, all of its stops get the current bus count — any later visit can only be worse, so the route is skipped. Every route and every stop entry is processed once.

Java

public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) return 0;
    Map<Integer, List<Integer>> routesAt = new HashMap<>();
    for (int i = 0; i < routes.length; i++) {
        for (int stop : routes[i]) {
            routesAt.computeIfAbsent(stop, x -> new ArrayList<>()).add(i);
        }
    }
    boolean[] boarded = new boolean[routes.length];
    Set<Integer> seen = new HashSet<>();
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(source);
    seen.add(source);
    int buses = 0;
    while (!queue.isEmpty()) {
        buses++;
        for (int size = queue.size(); size > 0; size--) {
            int stop = queue.poll();
            for (int bus : routesAt.getOrDefault(stop, List.of())) {
                if (boarded[bus]) continue;      // already fully used at a lower count
                boarded[bus] = true;
                for (int next : routes[bus]) {
                    if (next == target) return buses;
                    if (seen.add(next)) queue.offer(next);
                }
            }
        }
    }
    return -1;
}

Linear in total input size — the standard accepted solution.

Pro tip

The boarded[] check is the whole difference between TLE and AC — say out loud why revisiting a route can never help.

At a glance

Level	Approach	Time	Space
Brute Force	Route Graph via Pairwise Intersection	`O(R²·L)`	`O(R² + ∑L)`
Better	Stop-Level BFS with a Stop → Routes Index	`O(∑L_i²)`	`O(∑L)`
Optimal	Stop-Level BFS + Boarded-Route Marking	`O(∑L)`	`O(∑L)`

Common pitfalls

Forgetting source == target ⇒ 0, even when no route contains that stop.
Counting stops (edges between consecutive stops) instead of buses boarded.
Re-expanding the same route for every stop on it — quadratic on long routes.

Interview tips

Ask what a “move” costs: here it is a bus, which tells you what a BFS level means.
Contrast the stop graph (huge cliques) with the route graph (≤ 500 nodes).
Mention the stop → routes index as the key preprocessing step.

Pattern

BFS on a hyper-graph → when one action reaches a whole group of nodes, BFS over groups and mark each group used once.

My notes saved in this browser