> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Bus Routes Python Solution with Tests

> Tested Python solution for LeetCode 815 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 815, Hard. Topics: Array, Hash Table, Breadth-First Search. [View on LeetCode](https://leetcode.com/problems/bus-routes/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 815   # by problem number
lcpy gen -s bus_routes   # by problem name
```

## Problem

You are given an array `routes` representing bus routes where `routes[i]` is a bus route that the `i^th` bus repeats forever.

* For example, if `routes[0] = [1, 5, 7]`, this means that the `0^th` bus travels in the sequence `1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...` forever.

You will start at the bus stop `source` (You are not on any bus initially), and you want to go to the bus stop `target`. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from `source` to `target`. Return `-1` if it is not possible.

### Examples

```
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
```

```
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
```

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/bus_routes/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/bus_routes/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import defaultdict, deque


class Solution:
    # BFS over buses, not stops. Each bus is one hop. Map stop -> buses that
    # serve it. From source, enqueue all buses containing it; ride a bus to
    # reach every stop on it, transferring to unvisited buses at those stops.
    # Time: O(sum of routes length)
    # Space: O(sum of routes length)
    def num_buses_to_destination(self, routes: list[list[int]], source: int, target: int) -> int:
        if source == target:
            return 0

        stop_to_buses: dict[int, list[int]] = defaultdict(list)
        for bus, stops in enumerate(routes):
            for stop in stops:
                stop_to_buses[stop].append(bus)

        # source or target unreachable
        if source not in stop_to_buses or target not in stop_to_buses:
            return -1

        used_buses: set[int] = set()
        queue: deque[tuple[int, int]] = deque()
        for bus in stop_to_buses[source]:
            queue.append((bus, 1))
            used_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 not in used_buses:
                        used_buses.add(next_bus)
                        queue.append((next_bus, buses_taken + 1))

        return -1
```

## Complexity

| Time                    | Space                   |
| ----------------------- | ----------------------- |
| O(sum of routes length) | O(sum of routes length) |

## Tags

[Grind](/catalog/grind), [NeetCode All](/catalog/neetcode).