LeetCode 815: Bus Routes

Problem Restatement

We are given a list of bus routes.

Each routes[i] is the route of bus i. The bus repeats this route forever.

For example:

routes[0] = [1, 5, 7]

means bus 0 travels like this forever:

1 -> 5 -> 7 -> 1 -> 5 -> 7 -> ...

We start at bus stop source. We are not on any bus initially.

We want to reach bus stop target using buses only.

Return the minimum number of buses we need to take. If it is impossible, return -1. The official problem asks for the least number of buses needed from source to target.

Input and Output

Examples

Example 1:

routes = [[1, 2, 7], [3, 6, 7]]
source = 1
target = 6

We can take bus 0 from stop 1 to stop 7.

Then we transfer at stop 7 to bus 1.

Bus 1 reaches stop 6.

So the answer is:

2

Example 2:

routes = [[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]]
source = 15
target = 12

There is no sequence of bus transfers that connects stop 15 to stop 12.

So the answer is:

-1

First Thought: Search by Stops

One way to view the problem is as a graph of bus stops.

If two stops appear in the same route, we can travel between them using one bus.

But directly connecting every pair of stops in the same route can be expensive. A route with many stops would create many pairwise edges.

Instead, we should search by bus routes.

Taking one bus lets us reach all stops on that route. From those stops, we can transfer to other buses.

Key Insight

The cost is the number of buses taken, not the number of stops visited.

So BFS should advance by buses.

We build a map:

stop -> list of buses that visit this stop

Then we start from all buses that visit source.

Each BFS level means one more bus taken.

When a bus contains target, we return the current number of buses.

Algorithm

If:

source == target

return 0, because we are already there.

Build a hash map from stop to buses:

stop_to_buses[stop].append(bus_index)

Initialize a queue with every bus that visits source.

Each queue item stores:

(bus_index, buses_taken)

Use a set visited_buses so each bus route is processed at most once.

Then run BFS:

1. Pop a bus from the queue.
2. For every stop on that bus:
   1. If the stop is target, return buses_taken.
   2. For every other bus that visits this stop:
      1. If it has not been visited, mark it visited.
      2. Push it with buses_taken + 1.
3. If BFS ends, return -1.

Correctness

BFS explores states in increasing number of buses taken.

The initial states are exactly the buses we can board from source, each with cost 1.

When we process a bus, every stop on that bus is reachable using the recorded number of buses. From any of those stops, transferring to another bus costs exactly one additional bus. Therefore, each BFS edge has weight 1.

Because BFS on an unweighted graph visits states in shortest-distance order, the first time we reach a bus route that contains target, the current bus count is the minimum possible number of buses.

The visited_buses set does not remove any better answer. Once a bus has been reached with some number of buses, BFS guarantees that any later way to reach the same bus would use the same or more buses.

If BFS finishes without seeing target, then no reachable bus route can take us to the target stop, so the correct answer is -1.

Complexity

Let R be the number of routes, and let L be the total number of stops across all routes.

A stop may list several buses, but each bus is inserted into the queue at most once.

Implementation

from collections import defaultdict, deque

class Solution:
    def numBusesToDestination(
        self,
        routes: list[list[int]],
        source: int,
        target: int,
    ) -> int:
        if source == target:
            return 0

        stop_to_buses = defaultdict(list)

        for bus, route in enumerate(routes):
            for stop in route:
                stop_to_buses[stop].append(bus)

        queue = deque()
        visited_buses = set()

        for bus in stop_to_buses[source]:
            queue.append((bus, 1))
            visited_buses.add(bus)

        while queue:
            bus, buses_taken = queue.popleft()

            for stop in routes[bus]:
                if stop == target:
                    return buses_taken

                for next_bus in stop_to_buses[stop]:
                    if next_bus in visited_buses:
                        continue

                    visited_buses.add(next_bus)
                    queue.append((next_bus, buses_taken + 1))

        return -1

Code Explanation

We handle the simplest case first:

if source == target:
    return 0

If the source and target are the same stop, no bus is needed.

The map tells us which buses are available at each stop:

stop_to_buses = defaultdict(list)

We fill it by scanning every route:

for bus, route in enumerate(routes):
    for stop in route:
        stop_to_buses[stop].append(bus)

Then we start BFS from all buses that can be boarded at source:

for bus in stop_to_buses[source]:
    queue.append((bus, 1))
    visited_buses.add(bus)

The count is 1 because boarding one of these buses means we have taken one bus.

During BFS, we inspect every stop on the current bus:

for stop in routes[bus]:

If one of those stops is the target, we are done:

if stop == target:
    return buses_taken

Otherwise, every bus that also visits this stop is a possible transfer:

for next_bus in stop_to_buses[stop]:

We only process each bus once:

if next_bus in visited_buses:
    continue

If no reachable route reaches the target, return:

return -1

Testing

def run_tests():
    s = Solution()

    assert s.numBusesToDestination(
        [[1, 2, 7], [3, 6, 7]],
        1,
        6,
    ) == 2

    assert s.numBusesToDestination(
        [[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]],
        15,
        12,
    ) == -1

    assert s.numBusesToDestination(
        [[1, 2, 3]],
        1,
        3,
    ) == 1

    assert s.numBusesToDestination(
        [[1, 2, 3]],
        2,
        2,
    ) == 0

    assert s.numBusesToDestination(
        [[1, 2], [2, 3], [3, 4]],
        1,
        4,
    ) == 3

    print("all tests passed")

run_tests()