Design Connect-N winner detector
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### 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/
Quick Answer: This question evaluates data structure design and algorithmic optimization for grid-based game state management, including spatial reasoning required to detect n-in-a-row after a 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
Hints
- Track the height of each column to compute the landing row in O(1).
- Vertical check can be O(1) by maintaining, per column, the current top player's consecutive count.
- For horizontal and both diagonals, treat each line as a 1D set and maintain merged intervals of occupied indices for each (player, line-id).
- Use r - c as the key for main diagonals and r + c for anti-diagonals; use column index as the 1D coordinate.
- On each insertion, merge at most two adjacent intervals and track their lengths to detect k in O(1) average time.