1. Optimized Brute Force

Intuition

In Tic-Tac-Toe, a player wins by filling an entire row, column, or diagonal. After each move, we only need to check if that specific move creates a winning condition. Instead of checking the entire board, we focus on the row and column affected by the move, and check the diagonals only if the move is on one of them.

Algorithm

1. Initialize an n x n board with all cells set to 0.
2. When a player makes a move at position (row, col), mark that cell with the player's number.
3. Check if the player wins by:
   • Checking if all cells in the current row belong to the player.
   • Checking if all cells in the current column belong to the player.
   • If the move is on the main diagonal (row == col), check if all diagonal cells belong to the player.
   • If the move is on the anti-diagonal (col == n - row - 1), check if all anti-diagonal cells belong to the player.
4. Return the player number if any winning condition is met, otherwise return 0.

class TicTacToe:
    def __init__(self, n: int):
        self.board = [[0] * n for _ in range(n)]
        self.n = n
    
    def move(self, row: int, col: int, player: int) -> int:
        self.board[row][col] = player
        
        # check if the player wins
        if ((self._check_row(row, player)) or
            (self._check_column(col, player)) or
            (row == col and self._check_diagonal(player)) or
            (col == self.n - row - 1 and self._check_anti_diagonal(player))):
            return player
        
        # No one wins
        return 0
    
    def _check_diagonal(self, player: int) -> bool:
        for row in range(self.n):
            if self.board[row][row] != player:
                return False
        return True
    
    def _check_anti_diagonal(self, player: int) -> bool:
        for row in range(self.n):
            if self.board[row][self.n - row - 1] != player:
                return False
        return True
    
    def _check_column(self, col: int, player: int) -> bool:
        for row in range(self.n):
            if self.board[row][col] != player:
                return False
        return True
    
    def _check_row(self, row: int, player: int) -> bool:
        for col in range(self.n):
            if self.board[row][col] != player:
                return False
        return True

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n^2)$

Where $n$ is the size of the Tic-Tac-Toe board.

---

2. Optimized Approach

Intuition

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.

Algorithm

1. Initialize arrays to track the sum of moves for each row and column, plus two variables for the main diagonal and anti-diagonal.
2. 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.
3. Check if the absolute value of any counter equals n. If so, return the player number.
4. Return 0 if no winner yet.

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

Time & Space Complexity

• Time complexity: $O(1)$
• Space complexity: $O(n)$

Where $n$ is the size of the Tic-Tac-Toe board.

---

Common Pitfalls

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.

# Wrong
if row + col == n:  # Off by one error
    self.antiDiagonal += currentPlayer

# Correct
if col == n - row - 1:
    self.antiDiagonal += currentPlayer

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.

# The center cell (1,1) in a 3x3 board satisfies BOTH conditions:
# row == col (main diagonal)
# col == n - row - 1 (anti-diagonal)
# Both counters must be updated

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.

# Inefficient approach
self.rows_p1 = [0] * n
self.rows_p2 = [0] * n

# Optimal approach - single counter with +1/-1
self.rows = [0] * n
currentPlayer = 1 if player == 1 else -1
self.rows[row] += currentPlayer