Bus Routes — Hard Problem & Solution

routes[i] is the repeating loop of stops that bus i drives, for ever. For example a bus with route [1, 5, 7] drives 1 → 5 → 7 → 1 → 5 → 7 → ….

Difficulty: Hard
Topics: Arrays, Hash Table, Breadth-First Search
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

routes[i] is the repeating loop of stops that bus i drives, for ever. For example a bus with route [1, 5, 7] drives 1 → 5 → 7 → 1 → 5 → 7 → ….

You start at the stop source — not on any bus — and want to reach the stop target. Return the fewest buses you must ride, or -1 if the target cannot be reached. You may walk nowhere; travel only by bus.

Example 1

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: Ride the first bus from stop 1 to stop 7, then the second 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

Example 3

Input: routes = [[1,2,7]], source = 1, target = 1
Output: 0
Explanation: You are already there.

Constraints

1 <= routes.length <= 500
1 <= routes[i].length <= 10^5
All the values of routes[i] are unique.
sum(routes[i].length) <= 10^5
0 <= routes[i][j] < 10^6
0 <= source, target < 10^6

How to solve Bus Routes

Level-by-level BFS over stops where each level is one bus ride. Standing at any stop of a route, you can reach every other stop on that route for a single fare, so expanding a route means adding all of its stops at once.

Approach

Map each stop to the list of routes serving it.
Seed the queue with source; if it is already target, answer 0.
For each level, increment the bus count, then for every stop in the level take each unused route through it, mark the route used, and enqueue its unseen stops.
Return the count when target appears, or -1 when the queue empties.

Why it works

Marking a route as used, rather than only its stops, is what keeps the search linear in the total input size: a route with 100 000 stops is expanded once, no matter how many of its stops the search meets. It is safe because the first time the route is boarded is the cheapest, so re-boarding it later could never shorten a journey.

Complexity

Time — O(total stops + routes²) in the worst case
Space — O(total stops)

Pitfalls

source == target costs 0 buses, not 1.
Counting stops travelled instead of routes boarded answers a different question.
Without marking routes used, overlapping routes are re-expanded and the search blows up.

Reference solution

Python

from typing import List
from collections import defaultdict

def numBusesToDestination(routes: List[List[int]], source: int, target: int) -> int:
    if source == target:
        return 0
    stop_to_routes = defaultdict(list)
    for r, route in enumerate(routes):
        for s in route:
            stop_to_routes[s].append(r)
    used_route = [False] * len(routes)
    seen_stop = {source}
    q = [source]
    buses = 0
    while q:
        buses += 1
        nq = []
        for stop in q:
            for r in stop_to_routes.get(stop, ()):
                if used_route[r]:
                    continue
                used_route[r] = True
                for s in routes[r]:
                    if s == target:
                        return buses
                    if s in seen_stop:
                        continue
                    seen_stop.add(s)
                    nq.append(s)
        q = nq
    return -1

JavaScript

var numBusesToDestination = function(routes, source, target) {
    if (source === target) return 0;
    var r, i;
    var stopToRoutes = new Map();
    for (r = 0; r < routes.length; r++) {
        for (i = 0; i < routes[r].length; i++) {
            var s = routes[r][i];
            var list = stopToRoutes.get(s);
            if (list) list.push(r);
            else stopToRoutes.set(s, [r]);
        }
    }
    var usedRoute = [];
    for (r = 0; r < routes.length; r++) usedRoute.push(false);
    var seenStop = new Set();
    seenStop.add(source);
    var q = [source];
    var buses = 0;
    while (q.length > 0) {
        buses++;
        var nq = [];
        for (var k = 0; k < q.length; k++) {
            var rs = stopToRoutes.get(q[k]);
            if (!rs) continue;
            for (var a = 0; a < rs.length; a++) {
                var rt = rs[a];
                if (usedRoute[rt]) continue;
                usedRoute[rt] = true;
                for (var b = 0; b < routes[rt].length; b++) {
                    var stop = routes[rt][b];
                    if (stop === target) return buses;
                    if (seenStop.has(stop)) continue;
                    seenStop.add(stop);
                    nq.push(stop);
                }
            }
        }
        q = nq;
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue