Check Whether an n x n Tic-Tac-Toe Game Is Over (Win or Draw)
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the current state of an `n x n` tic-tac-toe board played by two players. A player wins by occupying all `n` cells of any row, any column, the main diagonal or the anti-diagonal. If every cell is occupied and nobody has won, the game is a draw.
Return whether the game is over, meaning that a player has won or the game is a draw.
Each cell holds `0` (empty), `1` (a mark of player 1) or `2` (a mark of player 2).
### Function Signature
```python
def game_over(board: list[list[int]]) -> bool:
```
### Rules
- A winning line is a row, a column, the main diagonal (cells `(i, i)`) or the anti-diagonal (cells `(i, n - 1 - i)`) whose `n` cells are all `1` or all `2`. A line whose cells are all `0` is not a winning line.
- Return `True` if the board has at least one winning line, or if no cell is `0`. Otherwise return `False`.
- The function only reports whether the game is over. It does not report who won, and a full board that also contains a winning line is simply over.
- Do not check whether the board could arise from a legal sequence of moves (for example, the difference between the two players' mark counts, or both players holding a winning line). Apply the rules to the board exactly as given.
- For `n = 1`, the single cell is a row, a column and both diagonals, so the game is over exactly when that cell is not `0`.
### Constraints
- `1 <= n <= 1000`, where `n = len(board)` and `len(board[i]) == n` for every row `i`
- Every cell is `0`, `1` or `2`.
- The board has at most 1,000,000 cells, so every count involved fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: board = [
[0, 0, 2],
[1, 2, 1],
[2, 1, 0]
]
Output: True
```
The anti-diagonal cells `(0, 2)`, `(1, 1)` and `(2, 0)` all hold `2`.
**Example 2**
```text
Input: board = [
[1, 2, 1],
[1, 2, 2],
[2, 1, 1]
]
Output: True
```
No row, column or diagonal holds a single player's marks, but no cell is empty, so the game is a draw.
**Example 3**
```text
Input: board = [
[1, 2, 0],
[0, 1, 0],
[2, 0, 0]
]
Output: False
```
The column at index `2` (the last column) is entirely empty, which is not a winning line. No other line holds a single player's marks, and empty cells remain.
Overview: Given an n x n tic-tac-toe board holding empty cells and two players' marks, decide whether the game is over because one player occupies an entire row, column or diagonal, or because the board is full with no winner. It tests complete line checks, draw detection and edge cases such as all-empty lines and a 1 x 1 board.
Read the full ByteDance Software Engineer interview experience this question came from
You are given the current state of an `n x n` tic-tac-toe board played by two players, as a square grid `board`. Each cell holds `0` (empty), `1` (a mark of player 1) or `2` (a mark of player 2). A player wins by occupying all `n` cells of any row, any column, the main diagonal or the anti-diagonal. If every cell is occupied and nobody has won, the game is a draw.
Return whether the game is over, meaning that a player has won or the game is a draw.
### Rules
- A winning line is a row, a column, the main diagonal (cells `(i, i)`) or the anti-diagonal (cells `(i, n - 1 - i)`) whose `n` cells are all `1` or all `2`. A line whose cells are all `0` is not a winning line.
- Return `True` if the board has at least one winning line, or if no cell is `0`. Otherwise return `False`.
- The function only reports whether the game is over. It does not report who won, and a full board that also contains a winning line is simply over.
- Do not check whether the board could arise from a legal sequence of moves (for example, the difference between the two players' mark counts, or both players holding a winning line). Apply the rules to the board exactly as given.
- For `n = 1`, the single cell is a row, a column and both diagonals, so the game is over exactly when that cell is not `0`.
The result is a boolean: `True`/`False` in Python, `true`/`false` in JavaScript, Java and C++.
### Example 1
```text
Input: board = [[0, 0, 2], [1, 2, 1], [2, 1, 0]]
Output: True
```
The anti-diagonal cells `(0, 2)`, `(1, 1)` and `(2, 0)` all hold `2`.
### Example 2
```text
Input: board = [[1, 2, 0], [0, 1, 0], [2, 0, 0]]
Output: False
```
The column at index `2` (the last column) is entirely empty, which is not a winning line. No other line holds a single player's marks, and empty cells remain.
### Constraints
- `1 <= n <= 1000`, where `n = len(board)` and `len(board[i]) == n` for every row `i`
- Every cell is `0`, `1` or `2`.
- The board has at most 1,000,000 cells, so every count involved fits in a 32-bit signed integer. No value in this problem exceeds 2^31 - 1, so a 32-bit `int` is sufficient in Java and C++.
Constraints
- 1 <= n <= 1000, where n = len(board) and len(board[i]) == n for every row i
- Every cell is 0, 1 or 2.
- The board has at most 1,000,000 cells, so every count involved fits in a 32-bit signed integer.
Examples
Input: ([[0]],)
Expected Output: False
Explanation: n = 1 with an empty cell: the only line is all 0, which is not a winning line, and an empty cell remains.
Input: ([[1]],)
Expected Output: True
Explanation: n = 1 with a player 1 mark: the single cell is a complete row, column and both diagonals.
Hints
- A game can be over for two independent reasons: some line is completely held by one player, or no cell is 0. Make sure both are considered.
- There are n rows, n columns and exactly two diagonals; in row i the anti-diagonal cell sits in column n - 1 - i.
- A line only counts when all of its cells hold the same value and that value is not 0.