# 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:

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

means bus `0` travels like this forever:

```python
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

| Item | Meaning |
|---|---|
| Input | `routes`, `source`, and `target` |
| Output | Minimum number of buses needed |
| Route meaning | Each `routes[i]` repeats forever |
| Transfer rule | We can transfer between buses at shared stops |
| Impossible case | Return `-1` |

## Examples

Example 1:

```python
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:

```python
2
```

Example 2:

```python
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:

```python
-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:

```python
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:

```python
source == target
```

return `0`, because we are already there.

Build a hash map from stop to buses:

```python
stop_to_buses[stop].append(bus_index)
```

Initialize a queue with every bus that visits `source`.

Each queue item stores:

```python
(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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(L)` | Building the map and processing each visited route’s stops |
| Space | `O(L)` | The stop-to-buses map and BFS storage |

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

## Implementation

```python
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:

```python
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:

```python
stop_to_buses = defaultdict(list)
```

We fill it by scanning every route:

```python
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`:

```python
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:

```python
for stop in routes[bus]:
```

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

```python
if stop == target:
    return buses_taken
```

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

```python
for next_bus in stop_to_buses[stop]:
```

We only process each bus once:

```python
if next_bus in visited_buses:
    continue
```

If no reachable route reaches the target, return:

```python
return -1
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[[1,2,7],[3,6,7]]` | Requires one transfer |
| Disconnected routes | Target is unreachable |
| One route contains both stops | One bus is enough |
| `source == target` | No bus needed |
| Transfer chain | Checks multiple BFS levels |