Bottom-Insertion Connect Game: Detect the First k-in-a-Row Winner
Company: Jane Street
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Two players, **B** and **R**, take turns dropping pieces onto a board that covers the upper half-plane of an integer grid. Columns are indexed by arbitrary integers (..., -2, -1, 0, 1, 2, ...), and rows are indexed 0, 1, 2, ... counting upward from the bottom.
A move is described by a pair `(player, column)` and is applied as follows:
- If the chosen column is empty, the new piece is placed at row 0 (the bottom cell of that column).
- If the column already contains pieces, **every piece in that column is pushed up by one row**, and the new piece is placed at row 0.
Pieces never move sideways, and a move never affects any column other than the one played.
Given a positive integer `k` and a chronological list of moves, process the moves one at a time. After a move is applied, a player **wins** if the board contains `k` consecutive occupied cells in a single row or in a single column that all hold that player's pieces. Diagonal lines do not count. Because a move shifts an entire column upward, a single move can change the row alignment of many pieces at once — so one move can simultaneously create winning lines for **both** players.
Determine the result of the game:
- If at least one player has a winning line after some move, stop at the **first** such move and return `[m, winners]`, where `m` is the 1-based index of that move and `winners` is the alphabetically sorted list of all players who hold a winning line at that moment (`["B"]`, `["R"]`, or `["B", "R"]`).
- If no player has a winning line after all moves have been applied, return `[-1, []]`.
### Input
- `k` — an integer, the required run length.
- `moves` — a list of moves in the order they are played; each move is a pair `[player, column]`, where `player` is the string `"B"` or `"R"` and `column` is an integer.
### Output
A pair `[m, winners]` as described above: the 1-based index of the first winning move and the alphabetically sorted list of winners at that moment, or `[-1, []]` if nobody wins.
### Constraints
- `1 <= k <= 50`
- `1 <= len(moves) <= 5000`
- `-10^6 <= column <= 10^6` (the board is unbounded — do not assume a fixed width)
- `player` is always `"B"` or `"R"`
### Example 1
```
k = 3
moves = [["B", 0], ["R", 5], ["B", 1], ["R", 5], ["B", 2]]
Output: [5, ["B"]]
```
After move 5, row 0 contains B pieces in columns 0, 1, and 2 — three consecutive B cells in a row, so B wins on move 5. (Column 5 holds two R pieces, which is not enough for `k = 3`.)
### Example 2
```
k = 3
moves = [["R", -1], ["B", -1], ["R", 0], ["B", 0], ["R", 1], ["B", 1]]
Output: [6, ["B", "R"]]
```
Each B move pushes the R piece in that column up to row 1 and lands at row 0. After move 6, row 0 contains B in columns -1, 0, 1 and row 1 contains R in columns -1, 0, 1. Both players complete a run of 3 on the same move, so both win simultaneously.
### Example 3
```
k = 3
moves = [["B", 0], ["R", 0], ["B", 0]]
Output: [-1, []]
```
All three pieces land in column 0. From bottom to top the column reads B, R, B (each new piece is inserted at the bottom, pushing the older pieces up), so there is no run of 3 anywhere and nobody wins.
Quick Answer: This question evaluates simulation and algorithmic problem-solving skills, focusing on state maintenance for an unbounded grid, efficient detection of k-in-a-row runs in rows and columns, and handling column-wise shifts that can produce simultaneous winners.
Two players, **B** and **R**, take turns dropping pieces onto a board covering the upper half-plane of an integer grid. Columns are indexed by arbitrary integers (..., -2, -1, 0, 1, 2, ...); rows are indexed 0, 1, 2, ... upward from the bottom.
A move `(player, column)` is applied as follows:
- If the chosen column is empty, the new piece is placed at row 0 (the bottom cell).
- If the column already contains pieces, **every piece in that column is pushed up by one row**, and the new piece is placed at row 0.
Pieces never move sideways, and a move never affects any other column.
Process the moves one at a time. After a move, a player **wins** if the board contains `k` consecutive occupied cells in a single row or a single column that all hold that player's pieces. Diagonals do not count. Because a move shifts an entire column upward, a single move can complete winning lines for **both** players at once.
Return `[m, winners]` for the **first** winning move — `m` is the 1-based move index and `winners` is the alphabetically sorted list of players holding a winning line at that moment (`["B"]`, `["R"]`, or `["B", "R"]`). If nobody wins after all moves, return `[-1, []]`.
### Input
- `k` — required run length.
- `moves` — list of `[player, column]` pairs in play order; `player` is `"B"` or `"R"`, `column` is an integer.
### Output
A pair `[m, winners]` as described, or `[-1, []]`.
### Example 1
```
k = 3
moves = [["B", 0], ["R", 5], ["B", 1], ["R", 5], ["B", 2]]
Output: [5, ["B"]]
```
After move 5, row 0 holds B in columns 0, 1, 2 — three in a row. Column 5 holds only two R pieces (not enough for k=3).
### Example 2
```
k = 3
moves = [["R", -1], ["B", -1], ["R", 0], ["B", 0], ["R", 1], ["B", 1]]
Output: [6, ["B", "R"]]
```
Each B move pushes the R piece in that column up to row 1. After move 6, row 0 has B in columns -1, 0, 1 and row 1 has R in columns -1, 0, 1 — both complete a run of 3 simultaneously.
### Example 3
```
k = 3
moves = [["B", 0], ["R", 0], ["B", 0]]
Output: [-1, []]
```
All three land in column 0; bottom-to-top it reads B, R, B, so no run of 3 exists anywhere.
### Constraints
- `1 <= k <= 50`
- `1 <= len(moves) <= 5000`
- `-10^6 <= column <= 10^6` (the board is unbounded — do not assume a fixed width)
- `player` is always `"B"` or `"R"`
Constraints
- 1 <= k <= 50
- 1 <= len(moves) <= 5000
- -10^6 <= column <= 10^6 (board is unbounded; do not assume a fixed width)
- player is always "B" or "R"
- Only horizontal (single-row) and vertical (single-column) runs count; diagonals do not
Examples
Input: (3, [['B', 0], ['R', 5], ['B', 1], ['R', 5], ['B', 2]])
Expected Output: [5, ['B']]
Explanation: After move 5, row 0 holds B in columns 0, 1, 2 — three in a row. Column 5 has only two R pieces, short of k=3.
Input: (3, [['R', -1], ['B', -1], ['R', 0], ['B', 0], ['R', 1], ['B', 1]])
Expected Output: [6, ['B', 'R']]
Explanation: Each B move pushes that column's R up to row 1. After move 6, row 0 is all B and row 1 is all R across columns -1,0,1 — both win on the same move.
Hints
- Model each column as a stack whose index 0 is the bottom row: dropping a piece is inserting at the front, which pushes every existing piece up by one row.
- A move only changes column c, but it shifts every piece in c to a new row — so after the move you must re-check c's vertical run AND every row that c occupies horizontally. Nothing outside column c changed.
- You never need to scan the whole board. If a winning line had existed before this move, an earlier move would already have returned. So only lines passing through the freshly played column can be new winners.
- For a horizontal check at row r, start at column c and walk left while the neighbor holds the same player, then walk right the same way; the total length is that row's run through c. Use a set to capture the case where the same move wins for both B and R.