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.