Design Tic-Tac-Toe
Problem
Design a TicTacToe game that is played on an n x n board between two players. Implement a move method that records a player's move and returns the current winning condition: the player number if they win with that move, or 0 if no one wins yet.
- 2 ≤ n ≤ 10⁴
- player is 1 or 2
- 0 ≤ row, col < n
- Moves are guaranteed to be valid and alternate between players
Example
n = 3, moves = [(0, 0, 1), (0, 2, 2), (2, 2, 1), (1, 1, 2), (2, 0, 1), (1, 0, 2), (2, 1, 1)][0, 0, 0, 0, 0, 0, 1]The game starts with an empty 3x3 board. Player 1 moves at (0,0), no winner yet (returns 0). Player 2 moves at (0,2), no winner yet (returns 0). Player 1 moves at (2,2), no winner yet (returns 0). Player 2 moves at (1,1), no winner yet (returns 0). Player 1 moves at (2,0), no winner yet (returns 0). Player 2 moves at (1,0), no winner yet (returns 0). Player 1 moves at (2,1), completing the bottom row and winning the game (returns 1). The key insight is that instead of checking the entire board after each move, the algorithm tracks counts per row, column, and diagonals, updating them incrementally and checking if any reach n or -n, indicating a win.
Approach
Straightforward Solution
A naive approach stores the entire board and after each move scans the entire row, column, and diagonals to check for a win, resulting in O(n) time per move and O(n^2) space.
Core Observation
A player wins if they fill an entire row, column, or diagonal with their marks. Tracking the entire board state and checking for a win after each move is inefficient for large n.
Path to Optimal
PreviewThe key insight is to maintain counters for each row, column, and the two diagonals that increment or decrement based on the player making the move. Player 1 increments by 1, Player 2 decrements by 1…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize arrays to track row and column counts, and variables for the two diagonals. For each move, update the corresponding row, column, and possibly diagonal counters by +1 or -1 depending on the player…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(1) per move
Each move updates at most four counters (one row, one column, and up to two diagonals) and checks their absolute values, all in constant time.
Space
O(n)
The solution uses two arrays of length n to track rows and columns, plus a constant number of variables for diagonals, resulting in O(n) auxiliary space.
Pattern Spotlight
Simulation (Incremental State Tracking)
Instead of re-examining the entire game state after each move, maintain incremental counters that reflect the current state, enabling constant-time win detection by tracking sums per row, column, and diagonals.
Solution
| 1 | class TicTacToe: |
| 2 | def __init__(self, n: int): |
| 3 | self.n = n |
| 4 | self.rows = [0] * n |
| 5 | self.cols = [0] * n |
| 6 | self.diag = 0 |
| 7 | self.anti_diag = 0 |
| 8 | |
| 9 | def move(self, row: int, col: int, player: int) -> int: |
| 10 | val = 1 if player == 1 else -1 |
| 11 | |
| 12 | self.rows[row] += val |
| 13 | self.cols[col] += val |
| 14 | |
| 15 | if row == col: |
| 16 | self.diag += val |
| 17 | |
| 18 | if row + col == self.n - 1: |
| 19 | self.anti_diag += val |
| 20 | |
| 21 | if ( |
| 22 | abs(self.rows[row]) == self.n |
| 23 | or abs(self.cols[col]) == self.n |
| 24 | or abs(self.diag) == self.n |
| 25 | or abs(self.anti_diag) == self.n |
| 26 | ): |
| 27 | return player |
| 28 | |
| 29 | return 0 |
Step-by-Step Solution
Initialize Counters to Track Rows, Columns, and Diagonals
| 3 | self.n = n |
| 4 | self.rows = [0] * n |
| 5 | self.cols = [0] * n |
| 6 | self.diag = 0 |
| 7 | self.anti_diag = 0 |
Objective
To set up data structures that efficiently track the cumulative moves per row, column, and diagonals for constant-time win detection.
Key Insight
By representing each player's move as +1 or -1, the counters accumulate the net effect of moves. This allows a single integer per row, column, or diagonal to represent the current state, avoiding the need to store the entire board or scan it repeatedly.
Interview Quick-Check
Core Logic
Using arrays for rows and columns and variables for diagonals enables O(1) updates and checks per move.
Common Pitfalls & Bugs
Forgetting to initialize the counters to zero or mixing up the indexing can cause incorrect tracking and false positives.
Update Counters and Detect Win After Each Move
To update the relevant counters based on the player's move and determine if the move results in a win.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
self.rows[row] += valUpdate the row counter for the move's row by adding the player's value.
Incrementing the row counter tracks the net moves in that row, enabling quick detection if a player fills the entire row.
self.cols[col] += valUpdate the column counter for the move's column by adding the player's value.
Incrementing the column counter tracks the net moves in that column, enabling quick detection if a player fills the entire column.
if (Start the conditional block that checks whether the move creates a winning row, column, or diagonal.
This condition begins a compound check that evaluates whether the current move completes any winning line by filling an entire row, column, or diagonal. Each component condition tests whether the accumulated counter for that line has reached ±n, indicating that one player occupies every position in that line.
Full line-by-line criticality + rationale for all 20 lines available on Pro.
Test Your Understanding
Why does tracking sums per row, column, and diagonal allow constant-time win detection?
See the answer with Pro.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Design Tic-Tac-Toe from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Design Tic-Tac-Toe drill