Check Whether an n x n Tic-Tac-Toe Game Is Over (Win or Draw)

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

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

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

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

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.

Is the N x N Tic-Tac-Toe Game Over?

Hints

1. 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.
2. There are n rows, n columns and exactly two diagonals; in row i the anti-diagonal cell sits in column n - 1 - i.
3. A line only counts when all of its cells hold the same value and that value is not 0.

Approach

Algorithm: scan the rows first. For each row, remember its first cell; the row is a winning line only if that first cell is non-zero and every cell of the row equals it. During the same scan, record whether any cell is 0. If a row wins, return True immediately. Otherwise check each column the same way (a column whose top cell is 0 is skipped, because a line containing a 0 can never be all 1 or all 2), then the main diagonal (i, i) anchored at (0, 0), then the anti-diagonal (i, n - 1 - i) anchored at (0, n - 1). If none of the 2n + 2 lines is a winning line, the game is over exactly when no cell is 0, so return the negation of the empty-cell flag.

Invariant and correctness: a line is winning if and only if all n of its cells equal one value v in {1, 2}. Comparing every cell of the line with its first cell and requiring that first cell to be non-zero is exactly this test, so all-0 lines and mixed 1/2 lines are both rejected. The only early exit returns True when a winning line exists, which is correct whether or not empty cells remain. If no row wins, every row has been scanned completely, so the empty-cell flag reflects every cell of the board when the final answer is computed. No move-legality checks are made, so boards with unequal mark counts or with both players holding winning lines are evaluated exactly as given.

Edge cases: n = 1 (the single cell is every line, so the answer is whether it is non-zero); all-zero boards (False); full boards with or without a winning line (True); lines that differ from uniform only in their first or last cell (not a win); the anti-diagonal uses column n - 1 - i, never n - i.

• Time complexity: O(n^2)
• Space complexity: O(1)