Design Tic-Tac-Toe
Medium · Arrays & Hashing · Explanation and code example
Optimized Approach
How it works
Rather than storing the entire board and checking all cells in a row, column, or diagonal after each move, we can maintain running counts. By using +1 for player 1 and -1 for player 2, we can track the cumulative sum for each row, column, and both diagonals. A player wins when any of these sums reaches +n or -n, indicating that all n cells in that line belong to the same player.
Steps
- Initialize arrays to track the sum of moves for each row and column, plus two variables for the main diagonal and anti-diagonal.
- When a player makes a move at position
(row, col):- Convert the player to
+1(player 1) or-1(player 2). - Add this value to the corresponding row and column counters.
- If the move is on the main diagonal (
row == col), update the diagonal counter. - If the move is on the anti-diagonal (
col == n - row - 1), update the anti-diagonal counter.
- Convert the player to
- Check if the absolute value of any counter equals
n. If so, return the player number. - Return
0if no winner yet.
Complexity
- Time complexity:
O(1) - Space complexity:
O(n)
Where
nis the size of the Tic-Tac-Toe board.
Things to watch for
Incorrect Anti-Diagonal Check
The anti-diagonal condition is often implemented incorrectly. Remember that for a cell to be on the anti-diagonal, the condition is col == n - row - 1, not row + col == n.
Forgetting the Center Cell in Odd-Sized Boards
For odd-sized boards (e.g., 3x3), the center cell lies on both diagonals. Failing to update both diagonal counters when a move is placed at the center will cause incorrect win detection.
Using Separate Counters Per Player
A common mistake is using separate counters for each player instead of a single counter with +1/-1 encoding. This doubles the space and complicates the win-checking logic.
Python code example
class TicTacToe:
def __init__(self, n: int):
self.rows = [0] * n
self.cols = [0] * n
self.diagonal = 0
self.antiDiagonal = 0
def move(self, row: int, col: int, player: int) -> int:
currentPlayer = 1 if player == 1 else -1
# update currentPlayer in rows and cols arrays
self.rows[row] += currentPlayer
self.cols[col] += currentPlayer
# update diagonal
if row == col:
self.diagonal += currentPlayer
# update anti diagonal
if col == (len(self.cols) - row - 1):
self.antiDiagonal += currentPlayer
n = len(self.rows)
# check if the current player wins
if (abs(self.rows[row]) == n or
abs(self.cols[col]) == n or
abs(self.diagonal) == n or
abs(self.antiDiagonal) == n):
return player
# No one wins
return 0
C++ code example
class TicTacToe {
public:
vector<int> rows;
vector<int> cols;
int diagonal;
int antiDiagonal;
TicTacToe(int n) {
rows.assign(n, 0);
cols.assign(n, 0);
diagonal = 0;
antiDiagonal = 0;
}
int move(int row, int col, int player) {
int currentPlayer = (player == 1) ? 1 : -1;
// update currentPlayer in rows and cols arrays
rows[row] += currentPlayer;
cols[col] += currentPlayer;
// update diagonal
if (row == col) {
diagonal += currentPlayer;
}
// update anti diagonal
if (col == (cols.size() - row - 1)) {
antiDiagonal += currentPlayer;
}
int n = rows.size();
// check if the current player wins
if (abs(rows[row]) == n ||
abs(cols[col]) == n ||
abs(diagonal) == n ||
abs(antiDiagonal) == n) {
return player;
}
// No one wins
return 0;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.