Detect a K-in-a-Row Win on a Rectangular Board
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Detect a K-in-a-Row Win on a Rectangular Board
Implement `winning_move(board, row, col, k)` after a valid move has placed a player's nonzero integer token at `(row, col)`. Return `true` iff that move creates at least `k` consecutive equal tokens horizontally, vertically, or on either diagonal.
Constraints: `1 <= rows, cols <= 1000`; `1 <= k <= max(rows, cols)`. Inspect only lines through the last move and use `O(1)` extra space.
```hint Count both directions
For each of four axes, combine the matching run on each side with the last move.
```
Quick Answer: Implement `winning_move(board, row, col, k)` after a valid move has placed a player's nonzero integer token at `(row, col)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
After a valid move places a player's nonzero integer token at `(row,col)`, return whether that move creates at least `k` consecutive equal tokens horizontally, vertically, or on either diagonal. Inspect only lines through the last move.
Constraints
- 1 <= rows, cols <= 1000 and board is rectangular.
- 1 <= k <= max(rows, cols).
- The move at (row, col) is valid and contains that player's nonzero integer token.
- Only horizontal, vertical, and the two diagonal lines through the last move can qualify.
Examples
Input: ([[7]], 0, 0, 1)
Expected Output: True
Explanation: A valid singleton move wins when k is one.
Input: ([[1, 1, 1]], 0, 1, 3)
Expected Output: True
Explanation: The last move joins matching tokens on both horizontal sides.
Hints
- Test k = 1, a run exactly k long, and a run one token too short.
- Include horizontal, vertical, and both diagonal wins with the move in the middle and at an edge.
- Use different and negative token values to confirm only exact equality contributes.