Fewest Buses to Ride Between Two Stops on Looping Bus Lines
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A city runs several bus lines. Each line drives a fixed loop of stops and repeats it forever, so a rider who boards a line can stay on from any of its stops to any other of its stops. You start at stop `source`, not on any bus, and want to reach stop `target`. You can board or leave a bus only at a stop on its line, and you change lines by leaving one bus at a stop that both lines serve.
Return the fewest buses you must board to travel from `source` to `target`, or `-1` if `target` cannot be reached.
### Function Signature
```python
def min_buses(routes: list[list[int]], source: int, target: int) -> int:
```
`routes[i]` lists the stops served by line `i` in the order its bus visits them; after the last stop the bus returns to the first. `source` and `target` are stop IDs.
### Rules
- Every boarding counts as one bus, including the first. Riding one line between any two of its stops counts as one bus, however many stops lie between them.
- If `source == target`, the answer is `0`, even when that stop is on no line.
- Otherwise, if no sequence of boardings reaches `target`, return `-1`. This includes a `source` or a `target` that no line serves.
- Riders change lines only at a shared stop; walking between different stops is not allowed.
- The answer is a single integer, so it is unique.
### Constraints
- `1 <= len(routes) <= 500`
- `1 <= len(routes[i]) <= 10^5`
- The total number of stops over all lines, `sum(len(r) for r in routes)`, is at most `10^5`.
- The stops within one line are distinct; the same stop may appear on many lines.
- `0 <= routes[i][j] < 10^6`
- `0 <= source, target < 10^6`
- All values fit in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: routes = [[2, 4, 9], [9, 11, 5], [5, 13], [4, 5]], source = 4, target = 13
Output: 2
```
Board line 3 at stop 4 and ride to stop 5, then board line 2 at stop 5 and ride to stop 13: two buses. One bus is not enough, because no single line serves both 4 and 13. Lines 0, 1 and 2 also connect the two stops (4 to 9, 9 to 5, 5 to 13), but that takes three buses.
**Example 2**
```text
Input: routes = [[1, 3, 5], [2, 4], [4, 8]], source = 3, target = 8
Output: -1
```
Stop 3 is served only by line 0, whose stops are 1, 3 and 5. None of those stops is on another line, so stop 8 cannot be reached.
**Example 3**
```text
Input: routes = [[7, 12]], source = 3, target = 3
Output: 0
```
The rider is already at the target, so no bus is needed, even though stop 3 is on no line.
Overview: A coding problem about bus lines that loop through fixed lists of stops: find the fewest buses a rider must board to travel from a source stop to a target stop, or report that the target cannot be reached. It tests modeling transfers between lines as a graph and keeping the search efficient when many lines share stops.
Read the full Pinterest Software Engineer interview experience this question came from
A city runs several bus lines. Each line drives a fixed loop of stops and repeats it forever, so a rider who boards a line can stay on from any of its stops to any other of its stops. You start at stop `source`, not on any bus, and want to reach stop `target`. You can board or leave a bus only at a stop on its line, and you change lines by leaving one bus at a stop that both lines serve.
Write `min_buses(routes, source, target)`, which returns the fewest buses you must board to travel from `source` to `target`, or `-1` if `target` cannot be reached.
`routes[i]` lists the stops served by line `i` in the order its bus visits them; after the last stop the bus returns to the first. `source` and `target` are stop IDs.
### Rules
- Every boarding counts as one bus, including the first. Riding one line between any two of its stops counts as one bus, however many stops lie between them.
- If `source == target`, the answer is `0`, even when that stop is on no line.
- Otherwise, if no sequence of boardings reaches `target`, return `-1`. This includes a `source` or a `target` that no line serves.
- Riders change lines only at a shared stop; walking between different stops is not allowed.
- The answer is a single integer, so it is unique.
### Constraints
- `1 <= len(routes) <= 500`
- `1 <= len(routes[i]) <= 10^5`
- The total number of stops over all lines, `sum(len(r) for r in routes)`, is at most `10^5`.
- The stops within one line are distinct; the same stop may appear on many lines.
- `0 <= routes[i][j] < 10^6`
- `0 <= source, target < 10^6`
- All values fit in a signed 32-bit integer. No input or output value can exceed 2^31 - 1, so a 32-bit `int` is sufficient in Java and C++.
### Example 1
```text
Input: routes = [[2, 4, 9], [9, 11, 5], [5, 13], [4, 5]], source = 4, target = 13
Output: 2
```
Board line 3 at stop 4 and ride to stop 5, then board line 2 at stop 5 and ride to stop 13: two buses. One bus is not enough, because no single line serves both 4 and 13. Lines 0, 1 and 2 also connect the two stops (4 to 9, 9 to 5, 5 to 13), but that takes three buses.
### Example 2
```text
Input: routes = [[1, 3, 5], [2, 4], [4, 8]], source = 3, target = 8
Output: -1
```
Stop 3 is served only by line 0, whose stops are 1, 3 and 5. None of those stops is on another line, so stop 8 cannot be reached.
Constraints
- 1 <= len(routes) <= 500
- 1 <= len(routes[i]) <= 10^5
- sum(len(r) for r in routes) <= 10^5 (total number of stops over all lines)
- The stops within one line are distinct; the same stop may appear on many lines.
- 0 <= routes[i][j] < 10^6
- 0 <= source, target < 10^6
- All values fit in a signed 32-bit integer; no input or output value exceeds 2^31 - 1.
Examples
Input: ([[2, 4, 9], [9, 11, 5], [5, 13], [4, 5]], 4, 13)
Expected Output: 2
Explanation: Source example 1: line 3 from 4 to 5, then line 2 from 5 to 13 is 2 buses; the path over lines 0, 1, 2 takes 3 buses and is not minimal.
Input: ([[1, 3, 5], [2, 4], [4, 8]], 3, 8)
Expected Output: -1
Explanation: Source example 2: stop 3 is only on line 0, which shares no stop with any other line, so target 8 is unreachable.
Hints
- Riding from one stop of a line to any other stop of the same line costs exactly one bus, however far apart they are in the list.
- Settle the special cases first: source == target costs 0 buses even on a stop no line serves, and a source or target that no line serves cannot be connected.
- Two lines are one change apart exactly when they share at least one stop; the cost you minimize is the number of lines used, not the number of stops passed.