Minimum Transfers Between Pin Boards
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Minimum Transfers Between Pin Boards
Implement `minimum_board_transfers(boards: list[list[int]], start_pin: int, target_pin: int) -> int`.
Each board is a route containing a set of pin identifiers. After boarding a route at any pin it contains, you may travel to any other pin on that same board. At a pin shared by two boards, you may transfer from one to the other. Return the minimum number of boards that must be boarded to travel from `start_pin` to `target_pin`.
### Input Domain
- `0 <= len(boards) <= 500`.
- The total number of pin occurrences across all boards is at most `100,000`.
- Pin identifiers and both endpoints are signed 32-bit integers.
- A board may list a pin more than once; duplicate occurrences have no additional effect.
### Output Rules
- If `start_pin = target_pin`, return `0`.
- Boarding the first route counts as one.
- Traveling between any two pins on the same board adds no further board.
- Return `-1` when no route exists.
### Constraints
- The answer must be the exact minimum number of boards boarded.
- Avoid comparing every pair of boards.
### Examples
#### Example 1
Input: `boards = [[1,2,7],[3,6,7]], start_pin = 1, target_pin = 6`
Output: `2`
#### Example 2
Input: `boards = [[1,5],[2,6]], start_pin = 1, target_pin = 6`
Output: `-1`
```hint Search by layers of boarded routes
Index each pin by the routes that contain it, and ensure a route or pin is expanded only once.
```
Quick Answer: Find the minimum number of pin boards needed to travel between two pins by searching shared routes without comparing every board pair.
Given a list of boards, where each board is a route containing pin identifiers, return the minimum number of boards that must be boarded to travel from start_pin to target_pin. After boarding a route at any pin it contains, you may travel to any other pin on that route at no additional board cost, and at a pin shared by two boards you may transfer between them. Boarding the first route counts as one. Return 0 when start_pin equals target_pin and -1 when no route exists. Duplicate occurrences of a pin on one board have no additional effect.
Constraints
- 0 <= len(boards) <= 500.
- The total number of pin occurrences across all boards is at most 100,000.
- Pin identifiers, start_pin, and target_pin are signed 32-bit integers.
- A board may list a pin more than once; duplicate occurrences have no additional effect.
- If start_pin equals target_pin, return 0; otherwise the first boarded route counts as one.
- Return -1 exactly when no route exists, and avoid comparing every pair of boards.
Examples
Input: ([], 5, 5)
Expected Output: 0
Explanation: Identical endpoints require no board even when no route contains the pin.
Input: ([[], []], 1, 2)
Expected Output: -1
Explanation: Empty routes cannot connect distinct endpoints.
Hints
- Think of the answer as layers of boarded routes.
- Index each pin by the routes that contain it, and avoid expanding the same route or pin more than once.