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
- 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.
- Player 1 contributes
+1and player 2 contributes-1to each relevant counter. - A player wins exactly when one of the counters they touch reaches
+n(player 1) or-n(player 2) in absolute value. - Each move updates four counters (row, column, main diagonal if
row == col, anti-diagonal ifrow + col == n - 1), so a move is O(1). - 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, notrow + col == norrow == n - 1 - colmisapplied. - 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.
🧩 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