⚡Flashcard Drill➔
NeetCode #31LC-348MediumArrays & HashingNC Algo100
← Back to All Problems

#31 · #348 · Design Tic-Tac-Toe(设计井字棋)

📌 Problem Statement & Constraints

Design a Tic-Tac-Toe game on an n x n board. Implement move(row, col, player) which records the move and returns the winning player (1 or 2) if this move completes a row, column, or diagonal; otherwise return 0. Constraints: 2 <= n <= 100; moves are always valid and always placed on an empty cell.

💡 Core Algorithmic Approaches

  1. Storing the whole board and re-scanning it after each move costs O(n) per move. Instead, maintain aggregate counters per row, per column, and for the two diagonals.
  2. Player 1 contributes +1 and player 2 contributes -1 to each relevant counter.
  3. A player wins exactly when one of the counters they touch reaches +n (player 1) or -n (player 2) in absolute value.
  4. Each move updates four counters (row, column, main diagonal if row == col, anti-diagonal if row + col == n - 1), so a move is O(1).
  5. The anti-diagonal condition is row + col == n - 1, which is easy to get wrong.

💻 Benchmark Python3 Implementation

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n                # +1 per player-1 mark, -1 per player-2
        self.cols = [0] * n
        self.diag = 0                      # main diagonal (row == col)
        self.anti = 0                      # anti-diagonal (row + col == n - 1)

    def move(self, row: int, col: int, player: int) -> int:
        v = 1 if player == 1 else -1
        self.rows[row] += v
        self.cols[col] += v
        if row == col:
            self.diag += v
        if row + col == self.n - 1:
            self.anti += v
        n = self.n
        if (abs(self.rows[row]) == n or abs(self.cols[col]) == n
                or abs(self.diag) == n or abs(self.anti) == n):
            return player
        return 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per move: four counter updates and four comparisons. Re-scanning the board would be O(n) per move.
💾 Space Complexity
O(n) for the row and column counters; the board itself is never materialised, which saves O(n^2).

⚠️ Interview Pitfalls & Follow-ups

  • Using the wrong anti-diagonal condition: it is row + col == n - 1, not row + col == n or row == n - 1 - col misapplied.
  • Only checking the row and column of the current move: a win can also be completed on a diagonal that does not pass through the row/column counters you just updated -- but it always passes through the current cell, so checking the diagonals that contain (row, col) is sufficient.
  • Forgetting abs: player 2 drives the counters negative, so the check must use absolute values.
  • Storing the board and scanning for a win: O(n) per move, which is the naive baseline.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems