Bus Routes

50 min · numBusesToDestination()

The shortest trip isn't about how many stops the bus passes. It's about how many times you have to board a bus.

routes[i] lists every stop visited by bus route i; that bus keeps cycling through its listed stops. You begin at stop source without being on a bus. Return the fewest buses you must take to reach stop target.

You may board any route containing your current stop, ride to any other stop on that route, then transfer to another route containing that stop.

Ground rules:

Return 0 when source == target — you don't need to board anything.
Return -1 when no chain of routes connects the two stops.
Count buses boarded, not stops visited or transfers made.

Constraints

1 <= routes.length <= 500
1 <= routes[i].length
The total number of stop entries across all routes is at most 100_000.
0 <= routes[i][j], source, target <= 1_000_000
Stops within one route are unique.

Hints

Choose the right state

Riding from one stop to another on the same route costs no extra bus. Boarding a new route is the action that increases the answer, so consider searching routes rather than individual stops.

Build the transfer board

Create an index from each stop to the route numbers that visit it. That turns "which buses can I transfer to here?" into a direct lookup.

One layer, one more bus

Seed the search with every route serving source, each at cost 1. A neighboring route shares at least one stop, and entering it adds exactly one bus.

Follow-up

If each route charged a different fare, how would you change the search to minimize total cost instead of buses boarded?

Visible cases

Examples

Example 1

ready

Input: routes = [ [ 1, 2, 7 ], [ 3, 6, 7 ] ] source = 1 target = 6
Expected: 2
Why: take the route serving 1 and 7, then transfer at 7 to the route serving 6

Example 2

ready

Input: routes = [ [ 4, 5 ], [ 8, 9 ] ] source = 4 target = 4
Expected: 0
Why: source and target are the same stop, so no bus is needed

Example 3

ready

Input: routes = [ [ 1, 2, 3 ], [ 7, 8, 9 ] ] source = 1 target = 9
Expected: -1
Why: the two route components share no transfer stop

Interview signal

Asked at

AmazonGoogleUber

Stop-by-stop route scan

One honest model keeps a queue of reachable stops. At each stop, scan every unused route to find buses that visit it. Boarding one of those buses makes every stop on that route reachable with one more bus.

from collections import deque
 
 
def num_buses_to_destination(
    routes: list[list[int]], source: int, target: int
) -> int:
    if source == target:
        return 0
 
    queue = deque([(source, 0)])
    seen_stops = {source}
    used_routes: set[int] = set()
 
    while queue:
        stop, buses = queue.popleft()
        if stop == target:
            return buses
 
        for route_index, route in enumerate(routes):
            if route_index in used_routes or stop not in route:
                continue
            used_routes.add(route_index)
            for next_stop in route:
                if next_stop not in seen_stops:
                    seen_stops.add(next_stop)
                    queue.append((next_stop, buses + 1))
 
    return -1

The search order is correct, but discovering which route serves a stop is expensive. With T total stop entries, repeated full route scans can dominate the trip.

Time O(T²) in the worst case. Space O(T) for queued stops and visited records.

State-space BFS over routes

The cost changes when you board a route, not when you pass another stop. Make each bus route the state. This is state-space BFS, breadth-first search over the thing whose transition adds exactly one unit to the answer.

First build a reverse index, a map from a stop to all route numbers containing it. Seed the queue with every route serving source at bus count 1. From a route, each stop reveals the routes available for the next transfer.

from collections import defaultdict, deque
 
 
def num_buses_to_destination(
    routes: list[list[int]], source: int, target: int
) -> int:
    if source == target:
        return 0
 
    stop_to_routes: dict[int, list[int]] = defaultdict(list)
    for route_index, route in enumerate(routes):
        for stop in route:
            stop_to_routes[stop].append(route_index)
 
    queue = deque()
    seen_routes: set[int] = set()
    for route_index in stop_to_routes.get(source, []):
        queue.append((route_index, 1))
        seen_routes.add(route_index)
 
    expanded_stops: set[int] = set()
    while queue:
        route_index, buses = queue.popleft()
        for stop in routes[route_index]:
            if stop == target:
                return buses
            if stop in expanded_stops:
                continue
            expanded_stops.add(stop)
            for next_route in stop_to_routes[stop]:
                if next_route not in seen_routes:
                    seen_routes.add(next_route)
                    queue.append((next_route, buses + 1))
 
    return -1

Mark a route when you enqueue it, and expand each stop's transfer list once. Those two guards prevent a busy interchange from multiplying the work.

Time O(T) — building the index and traversing all used route entries are linear in the total input size. Space O(T) for the index, queue, and visited sets.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayroutes: int[][] · source: int · target: int

Expected

Run: visible + custom · Submit: full suite