⚡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

中文速览与面试要点

设计井字棋

请在 n × n 的棋盘上,实现一个判定井字棋胜负的数据结构。实现 TicTacToe 类: __init__(n) 初始化棋盘; move(row, col, player) 表示玩家 player(1 或 2)在 (row, col) 落子,返回获胜的玩家编号(1 或 2),若无人获胜则返回 0。约束:2 ≤ n ≤ 100;player 为 1 或 2;每次 move 保证落子位置为空;最多调用 n^2 次 move。

核心要点

  • 朴素做法 :每次落子后扫描该行、该列、两条对角线,判断是否有 n 个相同棋子。单次 O(n),总计 O(n^3)。
  • 增量计数(标准解) :维护每行的累加值 rows[i] 、每列的 cols[j] 、主对角线 diag 、副对角线 anti 。
  • 玩家编码技巧 :玩家 1 的落子记 +1 ,玩家 2 记 -1 。这样若某行累加值的绝对值为 n,说明该行被同一玩家占满。
  • 判定条件 :落子后只检查 受影响的那一行、那一列与两条对角线 (副对角线仅在 row + col == n - 1 时受影响),若任一绝对值达到 n 则该玩家获胜。

常见陷阱

  • 每次 move 都扫描整行整列 :单次 O(n)、总计 O(n^3)。增量计数是本题的核心优化,务必写出来。
  • 用 0/1 表示玩家而不做符号编码 :若两个玩家都用 +1 计数,同一行被两人混合占据时累加值也会达到 n,导致误判。必须用 +1 / -1 区分。
  • 副对角线条件写成 row == col :主对角线是 row == col ,副对角线是 row + col == n - 1 ,两者必须区分。
  • 忘记 abs() :玩家 2 获胜时累加值为 -n,必须取绝对值再与 n 比较。

参考实现

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0        # 主对角线 (i == j)
        self.anti = 0        # 副对角线 (i + j == n - 1)

    def move(self, row: int, col: int, player: int) -> int:
        add = 1 if player == 1 else -1      # 玩家 1 记 +1,玩家 2 记 -1
        n = self.n
        self.rows[row] += add
        self.cols[col] += add
        if row == col:
            self.diag += add
        if row + col == n - 1:
            self.anti += add

        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