Bus Routes

Hard
947.

Bus Routes

Bus Routes is a hard coding problem on arrays, hash table and breadth-first search, asked in Amazon, Google, Uber and Snapchat interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} routes
 * @param {number} source
 * @param {number} target
 * @return {number}
 */
var numBusesToDestination = function(routes, source, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Bus Routes — Solution in Python, Java & C++

Bus Routes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Bus Routes is a hard coding problem on arrays, hash table and breadth-first search, asked in Amazon, Google, Uber and Snapchat interviews.

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

Hints for Bus Routes

  1. Hint 1

    Counting buses, not stops, is the whole point — so the search should move one route at a time.

  2. Hint 2

    Build a map from each stop to the routes that serve it.

  3. Hint 3

    Breadth-first search over stops, where one level is one bus ride, and never board the same route twice.

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

  1. Map each stop to the list of routes serving it.
  2. Seed the queue with source; if it is already target, answer 0.
  3. 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.
  4. 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

Java

public static int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) return 0;
    Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
    for (int r = 0; r < routes.length; r++) {
        for (int s : routes[r]) stopToRoutes.computeIfAbsent(s, x -> new ArrayList<>()).add(r);
    }
    boolean[] usedRoute = new boolean[routes.length];
    Set<Integer> seenStop = new HashSet<>();
    seenStop.add(source);
    List<Integer> q = new ArrayList<>();
    q.add(source);
    int buses = 0;
    while (!q.isEmpty()) {
        buses++;
        List<Integer> nq = new ArrayList<>();
        for (int stop : q) {
            List<Integer> rs = stopToRoutes.get(stop);
            if (rs == null) continue;
            for (int r : rs) {
                if (usedRoute[r]) continue;
                usedRoute[r] = true;
                for (int s : routes[r]) {
                    if (s == target) return buses;
                    if (!seenStop.add(s)) continue;
                    nq.add(s);
                }
            }
        }
        q = nq;
    }
    return -1;
}

C++

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    if (source == target) return 0;
    unordered_map<int, vector<int>> stopToRoutes;
    for (int r = 0; r < (int) routes.size(); r++) {
        for (int s : routes[r]) stopToRoutes[s].push_back(r);
    }
    vector<char> usedRoute(routes.size(), 0);
    unordered_set<int> seenStop;
    seenStop.insert(source);
    vector<int> q = { source };
    int buses = 0;
    while (!q.empty()) {
        buses++;
        vector<int> nq;
        for (int stop : q) {
            auto it = stopToRoutes.find(stop);
            if (it == stopToRoutes.end()) continue;
            for (int r : it->second) {
                if (usedRoute[r]) continue;
                usedRoute[r] = 1;
                for (int s : routes[r]) {
                    if (s == target) return buses;
                    if (!seenStop.insert(s).second) continue;
                    nq.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets