Determine Pin Connections Through Common Boards

Scenario

Pinterest boards contain many pins; need to infer relationships between pins.

Question

Given the membership lists of all boards, write a function that returns whether two pins are connected through any sequence of common boards. Follow-up: return the minimum number of boards required to connect the two pins.

Hints

Model boards/pins as a bipartite graph; BFS from one pin over boards to the other.

Part 1: Determine Whether Two Pins Are Connected

You are given boards, where each board is a list of pin IDs. Two pins are considered connected if you can start at start_pin and repeatedly do the following: move from a pin to any board that contains it, then move from that board to any pin on that same board. Return whether end_pin is reachable.

Equivalently, you are checking whether there exists any chain of overlapping boards that connects the two pins.

A pin is always considered connected to itself, even if it does not appear in any board.

Constraints

• 0 <= len(boards) <= 10^4
• 0 <= sum(len(board) for board in boards) <= 2 * 10^5
• Pin IDs are integers
• Boards may contain duplicate pin IDs; duplicates should not change the answer

Examples

Example 1

Input: ([[1, 2, 3], [3, 4], [6, 7]], 1, 4)
Output: True

Explanation: Pin 1 shares board 0 with pin 3, and pin 3 shares board 1 with pin 4.

Example 2

Input: ([[1, 2], [3, 4], [5]], 1, 5)
Output: False

Explanation: There is no chain of boards connecting pin 1 to pin 5.

Hints

1. Think of pins and boards as a bipartite graph: pin -> board -> pin.
2. Use BFS or DFS, but make sure to mark both visited pins and visited boards so you do not reprocess the same board many times.

Part 2: Minimum Number of Boards Needed to Connect Two Pins

You are given boards, where each board is a list of pin IDs. You may move from a pin to any board that contains it, then from that board to any pin on the same board. Return the minimum number of boards used in any valid connection from start_pin to end_pin.

If both pins are on the same board, the answer is 1. If start_pin == end_pin, the answer is 0. If no connection exists, return -1.

Constraints

• 0 <= len(boards) <= 10^4
• 0 <= sum(len(board) for board in boards) <= 2 * 10^5
• Pin IDs are integers
• Boards may contain duplicate pin IDs; duplicates should not change the answer

Examples

Example 1

Input: ([[1, 2, 3], [3, 4], [4, 5]], 1, 5)
Output: 3

Explanation: One shortest path is 1 -> board[0] -> 3 -> board[1] -> 4 -> board[2] -> 5, which uses 3 boards.

Example 2

Input: ([[1, 2], [2, 3]], 1, 2)
Output: 1

Explanation: Pins 1 and 2 already share the first board.

Hints

1. Run BFS starting from the start pin, and treat traversing one board as adding 1 to the distance.
2. If you mark a board as visited the first time you process it, you avoid counting the same board multiple times and keep the search efficient.