Katkat
Back

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

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.