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
The 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. If any counter reaches +n or -n, that player wins. This reduces the per-move time complexity to O(1) and space to O(n).
Optimal Approach
Initialize 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. Check if any counter's absolute value equals n, indicating a win. Return the player number if so, else 0.
Time
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
| 10 | val = 1 if player == 1 else -1 |
| 12 | self.rows[row] += val |
| 13 | self.cols[col] += val |
| 15 | if row == col: |
| 16 | self.diag += val |
| 18 | if row + col == self.n - 1: |
| 19 | self.anti_diag += val |
| 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 |
| 29 | return 0 |
Objective
To update the relevant counters based on the player's move and determine if the move results in a win.
Key Insight
Incrementing or decrementing counters by +1 or -1 depending on the player encodes the player's presence. Checking if any counter reaches the absolute value of n immediately reveals a winning line. This approach avoids scanning the board and reduces the per-move complexity to constant time.
Interview Quick-Check
Core Logic
The move method updates the row, column, and diagonal counters and returns the player if any counter's absolute value equals n.
State & Boundaries
Diagonal counters are updated only if the move lies on the main diagonal (row == col) or anti-diagonal (row + col == n - 1).
Common Pitfalls & Bugs
Failing to check both diagonals or incorrectly calculating the anti-diagonal condition can cause missed wins.
Complexity
Each move runs in O(1) time, updating at most four counters and performing constant-time checks.
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.
abs(self.rows[row]) == self.nCheck if the absolute value of the row counter equals n, indicating a win.
If the absolute sum equals n, it means one player has filled the entire row, guaranteeing a win.
or abs(self.cols[col]) == self.nCheck if the absolute value of the column counter equals n, indicating a win.
If the absolute sum equals n, it means one player has filled the entire column, guaranteeing a win.
or abs(self.diag) == self.nCheck if the absolute value of the main diagonal counter equals n, indicating a win.
If the absolute sum equals n, it means one player has filled the entire main diagonal, guaranteeing a win.
or abs(self.anti_diag) == self.nCheck if the absolute value of the anti-diagonal counter equals n, indicating a win.
If the absolute sum equals n, it means one player has filled the entire anti-diagonal, guaranteeing a win.
self.rows = [0] * nInitialize an array to track the sum of moves per row.
This array accumulates the net effect of player moves per row, enabling constant-time win detection by row.
self.cols = [0] * nInitialize an array to track the sum of moves per column.
This array accumulates the net effect of player moves per column, enabling constant-time win detection by column.
self.diag += valUpdate the main diagonal counter by adding the player's value.
This update tracks the net moves on the main diagonal, enabling constant-time win detection on this diagonal.
self.anti_diag += valUpdate the anti-diagonal counter by adding the player's value.
This update tracks the net moves on the anti-diagonal, enabling constant-time win detection on this diagonal.
return playerIf any winning condition is met, return the player number.
Returning the player immediately upon detecting a winning line ensures correct and efficient termination of the move method.
self.diag = 0Initialize a variable to track the sum of moves on the main diagonal.
Tracking the main diagonal separately allows constant-time detection of diagonal wins without scanning the board.
self.anti_diag = 0Initialize a variable to track the sum of moves on the anti-diagonal.
Tracking the anti-diagonal separately allows constant-time detection of anti-diagonal wins without scanning the board.
val = 1 if player == 1 else -1Assign the value representing the current player.
This assignment is critical to ensure consistent updates to counters reflecting the player's move.
if row == col:Check if the move is on the main diagonal (row equals column).
Only moves on the main diagonal affect the main diagonal counter, so this condition ensures correct updates.
if row + col == self.n - 1:Check if the move is on the anti-diagonal (row + column equals n - 1).
Only moves on the anti-diagonal affect the anti-diagonal counter, so this condition ensures correct updates.
return 0Return 0 if no winning condition is met after the move.
Returning 0 signals that the game continues with no winner after this move, maintaining correct game state.
):Close the compound conditional expression that checks for any winning row, column, or diagonal.
This parenthesis closes the grouped logical expression that evaluates all potential winning lines. Grouping the conditions ensures that the entire set of win checks is evaluated together before the conditional block executes.
self.n = nStore the board size n as an instance variable.
The board size n is fundamental for indexing and boundary checks throughout the game logic.
Test Your Understanding
Why does tracking sums per row, column, and diagonal allow constant-time win detection?
Because each player's move increments or decrements these counters, and a counter reaching +n or -n means one player has filled that entire line, guaranteeing a win without scanning the entire board.
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