Katkat
Back

Report the winner after each move on an n-by-n tic-tac-toe board

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Coding problem: replay an n-by-n tic-tac-toe game from a list of moves and report after every move whether the player who just moved has filled a row, a column or either diagonal. It tests efficient win detection on large boards and careful handling of diagonal and anti-diagonal cells.

Two players play a generalized game of tic-tac-toe on an n × n board. The players are numbered 1 and 2, and each move places the moving player'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, return the result of the game immediately after each move.

Function Signature

def tic_tac_toe_results(n: int, moves: list[list[int]]) -> list[int]:

moves[i] = [row, col, player] means that player player places a mark on the cell in row row and column col, both 0-indexed.

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, or 0 if nobody has won yet. Only the player who just moved can have just won.
  • Moves are applied in the given order, and each move targets a cell that is still empty. The input does not have to alternate between the players; do not check whose turn it is.
  • The game ends at the first winning move, and no moves follow it, so only the last result can be nonzero.
  • Return one result per move, in move order.

Constraints

  • 2 <= n <= 100
  • 1 <= len(moves) <= n * n
  • 0 <= row, col < n, and no two moves use the same cell
  • player is 1 or 2
  • No move comes after a winning move

Examples

Example 1

Input: n = 3, moves = [[1, 1, 1], [0, 0, 2], [0, 2, 1], [2, 0, 2], [1, 0, 1], [2, 2, 2], [1, 2, 1]]
Output: [0, 0, 0, 0, 0, 0, 1]

The last move gives player 1 the cells (1, 0), (1, 1) and (1, 2), the whole middle row. Before it, no row, column or diagonal belonged entirely to one player.

Example 2

Input: n = 2, moves = [[0, 1, 2], [1, 1, 1], [1, 0, 2]]
Output: [0, 0, 2]

Player 2 moves first and completes the anti-diagonal (0, 1), (1, 0) on the third move.

Example 3

Input: n = 4, moves = [[0, 0, 2], [0, 1, 1], [1, 1, 2], [0, 2, 1], [2, 2, 2]]
Output: [0, 0, 0, 0, 0]

Player 2 holds three of the four cells of the main diagonal, which is not a win on a 4 × 4 board, so the game is still undecided after every move.