Design Connect-N winner detector

Question

Design a data structure for the Connect-N game: pieces are dropped into a column (occupying the lowest empty cell). Implement move(column, player) that returns true if, after the move, the player has n consecutive pieces horizontally, vertically, or diagonally. Optimize the per-move time complexity and explain the algorithm.

https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/description/

Connect-N Winner Detection Per Move

You are given an empty rows-by-cols grid for a Connect-N style game and a sequence of moves. Each move is (column, player). A piece drops into the specified column and occupies the lowest empty cell in that column. After each move, determine whether the just-moved player has at least k consecutive pieces in any direction: horizontal, vertical, main diagonal (r - c constant), or anti-diagonal (r + c constant). Return a list of booleans of the same length as moves, where the i-th value is true if move i results in a win for that player, otherwise false.

Constraints

• 1 <= rows, cols <= 2000
• 1 <= k <= max(rows, cols)
• 1 <= len(moves) <= rows * cols
• 0 <= column < cols
• Players are positive integers (more than two players allowed)
• All moves are valid; no column is overfilled

Examples

Example 1

Input: rows = 6, cols = 7, k = 4, moves = [(3,1),(2,2),(3,1),(2,2),(3,1),(2,2),(3,1)]
Output: [false, false, false, false, false, false, true]

Explanation: Player 1 stacks four vertically in column 3 on the last move.

Example 2

Input: rows = 6, cols = 7, k = 4, moves = [(0,2),(1,1),(1,2),(2,1),(2,1),(2,2),(3,1),(3,1),(3,1),(3,2)]
Output: [false, false, false, false, false, false, false, false, false, true]

Explanation: Player 2 forms a main diagonal of length 4: (r,c) = (0,0),(1,1),(2,2),(3,3) with required supports.

Hints

1. Track the height of each column to compute the landing row in O(1).
2. Vertical check can be O(1) by maintaining, per column, the current top player's consecutive count.
3. For horizontal and both diagonals, treat each line as a 1D set and maintain merged intervals of occupied indices for each (player, line-id).
4. Use r - c as the key for main diagonals and r + c for anti-diagonals; use column index as the 1D coordinate.
5. On each insertion, merge at most two adjacent intervals and track their lengths to detect k in O(1) average time.

Approach

Maintain per-column height to place each piece in O(1). Vertical detection is O(1) by tracking, for each column, the top run: the player at the top and its consecutive count; inserting a new piece either extends that run or starts a new run of length 1. For horizontal and diagonal directions, model each line as a 1D number line and maintain merged intervals of occupied indices for each (player, line-id) using two hash maps: start_to_end and end_to_start. When inserting index x, you only need to check whether there is a segment ending at x-1 and/or starting at x+1; merge them with x accordingly, which is O(1) average time. Line identifiers are: row for horizontal, r - c for main diagonals, and r + c for anti-diagonals. Using column as the coordinate along a line makes adjacency checks simple. If any direction reaches length k after a move, that move is a winning move.

• Time complexity: O(1) average per move
• Space complexity: O(M), where M is the number of moves