Report the Winner After Every Move on an n x n Tic-Tac-Toe Board
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Two players play tic-tac-toe on an `n × n` board, a generalization of the classic `3 × 3` game. Player 1 makes the first move and the players then alternate; each move places the mover's mark on an empty cell. A player wins as soon as their marks fill an entire row, an entire column, the main diagonal or the anti-diagonal.
Given `n` and the moves in the order they are played, report the state of the game after every move.
### Function Signature
```python
def winner_after_each_move(n: int, moves: list[list[int]]) -> list[int]:
```
`moves[i] = [row, col]` is the cell, 0-indexed, taken by move `i`. Move `i` is made by player 1 when `i` is even and by player 2 when `i` is odd.
### Rules
- The main diagonal is the cells `(i, i)` and the anti-diagonal is the cells `(i, n - 1 - i)`, for `0 <= i < n`.
- The result after a move is the number of the player who has won (1 or 2), or 0 if nobody has won yet.
- The game stops at the first winning move: the input never contains a move after it, so only the last result can be nonzero.
- If the moves end without a winner (including a full board, which is a draw), every result is 0.
- When `n = 1`, the first move fills a whole row, so player 1 wins immediately.
- Return exactly one result per move, in move order.
### Constraints
- `1 <= n <= 1000`
- `1 <= len(moves) <= min(n * n, 100000)`
- `0 <= row, col < n`, and no two moves use the same cell
- No move follows a winning move
### Examples
**Example 1**
```text
Input: n = 3, moves = [[0, 0], [1, 1], [0, 1], [2, 2], [0, 2]]
Output: [0, 0, 0, 0, 1]
```
Player 1 takes `(0, 0)`, `(0, 1)` and `(0, 2)` on moves 0, 2 and 4, completing the top row on the last move. Player 2's cells `(1, 1)` and `(2, 2)` lie on the main diagonal, but `(0, 0)` belongs to player 1.
**Example 2**
```text
Input: n = 4, moves = [[0, 0], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 3]]
Output: [0, 0, 0, 0, 0, 0, 0, 2]
```
After move 4, player 1 holds three of the four main-diagonal cells, which is not a win on a `4 × 4` board. Player 2's last move completes column 3: `(0, 3)`, `(1, 3)`, `(2, 3)` and `(3, 3)`.
**Example 3**
```text
Input: n = 3, moves = [[0, 0], [1, 1], [0, 2], [0, 1], [2, 1], [1, 2], [1, 0], [2, 0], [2, 2]]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 0]
```
The board fills up without a winner. The final position, by player number, is:
```text
1 2 1
1 2 2
2 1 1
```
Overview: Process a sequence of alternating tic-tac-toe moves on an n x n board and report, after every move, whether player 1 or player 2 has just completed a full row, column, main diagonal or anti-diagonal. Tests efficient incremental win detection, diagonal indexing and correct handling of draws.
Read the full Databricks Software Engineer interview experience this question came from
Two players play tic-tac-toe on an `n x n` board, a generalization of the classic `3 x 3` game. Player 1 makes the first move and the players then alternate; each move places the mover's mark on an empty cell. A player wins as soon as their marks fill an entire row, an entire column, the main diagonal or the anti-diagonal.
You are given `n` and the list `moves` in the order the moves are played. `moves[i] = [row, col]` is the cell, 0-indexed, taken by move `i`. Move `i` is made by player 1 when `i` is even and by player 2 when `i` is odd.
Return a list with exactly one result per move, in move order. The result after a move is the number of the player who has won (`1` or `2`), or `0` if nobody has won yet.
### Rules
- The main diagonal is the cells `(i, i)` and the anti-diagonal is the cells `(i, n - 1 - i)`, for `0 <= i < n`.
- The game stops at the first winning move: the input never contains a move after it, so only the last result can be nonzero.
- If the moves end without a winner (including a full board, which is a draw), every result is `0`.
- When `n = 1`, the first move fills a whole row, so player 1 wins immediately.
### Constraints
- `1 <= n <= 1000`
- `1 <= len(moves) <= min(n * n, 100000)`
- `moves[i] = [row, col]` with `0 <= row, col < n`, and no two moves use the same cell
- No move follows a winning move
- Every input value and every result fits in a 32-bit signed integer
### Example 1
```text
Input: n = 3, moves = [[0, 0], [1, 1], [0, 1], [2, 2], [0, 2]]
Output: [0, 0, 0, 0, 1]
```
Player 1 takes `(0, 0)`, `(0, 1)` and `(0, 2)` on moves 0, 2 and 4, completing the top row on the last move. Player 2's cells `(1, 1)` and `(2, 2)` lie on the main diagonal, but `(0, 0)` belongs to player 1.
### Example 2
```text
Input: n = 4, moves = [[0, 0], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 3]]
Output: [0, 0, 0, 0, 0, 0, 0, 2]
```
After move 4, player 1 holds three of the four main-diagonal cells, which is not a win on a `4 x 4` board. Player 2's last move completes column 3: `(0, 3)`, `(1, 3)`, `(2, 3)` and `(3, 3)`.
Constraints
- 1 <= n <= 1000
- 1 <= len(moves) <= min(n * n, 100000)
- moves[i] = [row, col] with 0 <= row, col < n, and no two moves use the same cell
- No move follows a winning move, so only the last result can be nonzero
- Every input value and every result fits in a 32-bit signed integer
Examples
Input: (3, [[0, 0], [1, 1], [0, 1], [2, 2], [0, 2]])
Expected Output: [0, 0, 0, 0, 1]
Explanation: Source Example 1: player 1 completes the top row on move 4 (row win by player 1).
Input: (4, [[0, 0], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 0], [3, 3]])
Expected Output: [0, 0, 0, 0, 0, 0, 0, 2]
Explanation: Source Example 2: player 1 holds 3 of 4 main-diagonal cells (no win); player 2 completes column 3 on move 7.
Hints
- A move can only complete a line that passes through the cell it takes: its row, its column, and a diagonal only when the cell lies on that diagonal.
- A line is won only when all n of its cells belong to one player; a line holding marks from both players can never be won, and n - 1 cells are not enough.
- On an odd board the center cell lies on both diagonals; on an even board the two diagonals share no cell.
Community answers
Answer by samreddy7406711653
My approach is to maintain counters for each row, column, and the two diagonals, separately for both players.
Each counter starts at n. It represents how many more cells that player needs to fill to complete that line.
We process the moves in order. Even-indexed moves belong to player 1, and odd-indexed moves belong to player 2.
For a move at (row, col), decrement the current player’s row and column counters. If row == col, also decrement their main-diagonal counter. If row + col == n - 1, decrement their anti-diagonal counter.
These diagonal checks should be separate if statements because the centre cell on an odd-sized board belongs to both diagonals.
If any affected counter reaches zero, the current player has completed a line, so append their player number to the result. Otherwise, append 0.
We don’t need to scan the board after each move or even store the board, since the question guarantees valid moves with no repeated cells.
Each move takes O(1) time. For m moves, total time is O(n + m), including initialisation. Auxiliary space is O(n), plus O(m) for the output.