You are implementing a sparse, unbounded variant of Connect Four. The board has one vertical stack for every integer column index, including negative indices, so it extends endlessly in both horizontal directions. Each column also has no height limit. A newly dropped piece falls to the top of its column: if the column already contains h pieces, the new piece occupies row h, where row 0 is the bottom cell.
Several players take part, each identified by an integer ID. A player wins as soon as they have at least n of their own pieces in an unbroken line, either:
n consecutive pieces in one column, orn consecutive pieces in the same row across consecutive columns.Columns fill independently, so adjacent columns can have very different heights. For a horizontal run at row r, each required cell must actually contain that player's piece at row r; an empty cell or an opponent's piece interrupts the run.
Your task is to process an ordered list of moves. For each move (col, player), drop the piece into column col, then report true if this move creates a winning run of length at least n for the moving player, and false otherwise. Continue processing every move even after a win has occurred.
The board is too large to scan in full. Each insertion should inspect only the local area affected by the new piece and take $$O(n)$$ time; total memory usage should be proportional to the number of placed pieces.
Input Format:
n and m: the required run length and the number of moves.m lines contains two integers col and player.Output Format:
For each move, print one line containing true or false.
Example 1:
Input:
3 6
1 1
2 1
3 2
1 1
2 1
3 1
Output:
false
false
false
false
false
true
Explanation: The last move places player 1 at row 1 of column 3. Row 1 now contains player 1 pieces in columns 1, 2, and 3, forming a horizontal run of length 3.
n = 3 moves = [[1,1], [2, 1], [3, 2], [1, 1], [2, 1], [3, 1]]
false false false false false true
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | null | null | null |
| 1 | null | null | null |
Input: n = 3 and 6 moves. The board starts empty; we show columns 1, 2, 3 and rows 0 (bottom) and 1.
Example 2:
Input:
4 5
7 2
100 1
7 2
7 2
7 2
Output:
false
false
false
false
true
Explanation: The final move places player 2 at row 3 of column 7. Column 7 now has player 2 pieces in rows 0 through 3, completing a vertical run of length 4.
Constraints:
$$1 \le player \le 2,000,000,000$$$$O(n)$$ time or better.n = 3 moves = [[1,1], [2, 1], [3, 2], [1, 1], [2, 1], [3, 1]]
false false false false false true
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | null | null | null |
| 1 | null | null | null |
Input: n = 3 and 6 moves. The board starts empty; we show columns 1, 2, 3 and rows 0 (bottom) and 1.