Solution Explanation: Design Tic-Tac-Toe

This problem requires designing a TicTacToe class that simulates a tic-tac-toe game on an n x n board. The core challenge lies in efficiently determining the winner after each move. A naive approach of checking all rows, columns, and diagonals after every move would lead to an $O(n^2)$ time complexity for each move() operation. The optimal solution achieves $O(1)$ time complexity per move.

Approach: Optimized Counting

The key to achieving $O(1)$ time complexity is to maintain a concise representation of the board state. Instead of storing the entire board, we use several arrays to track the number of marks each player has placed in each row, column, and both diagonals.

We use two arrays, one for each player (player 1 and player 2). Each array has a size of 2n + 2.

• Rows (0 to n-1): The first n elements represent rows. array[i] stores the number of marks placed in row i.
• Columns (n to 2n-1): The next n elements represent columns. array[n + i] stores the number of marks in column i.
• Main Diagonal (2n): array[2n] tracks the count of marks on the main diagonal (top-left to bottom-right).
• Anti-Diagonal (2n + 1): array[2n + 1] tracks the count of marks on the anti-diagonal (top-right to bottom-left).

move(row, col, player) function:

1. Update Counts: When a player makes a move at (row, col), we increment the corresponding row, column, and diagonal counts in the player's array.
2. Check for Win: After updating the counts, we check if any of the row, column, or diagonal counts for the current player has reached n (the board size). If so, that player wins, and the function returns the player's ID.
3. Return 0: If no player has won, the function returns 0.

Time Complexity: Each move() operation involves a constant number of array accesses and comparisons, regardless of the board size. Therefore, the time complexity is O(1).

Space Complexity: The space complexity is O(n) because we use arrays of size 2n+2 to store the counts for each player.

Code Implementation (Python)

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [[0, 0] for _ in range(n)]  # rows[i][player-1] counts for player in row i
        self.cols = [[0, 0] for _ in range(n)]  # cols[i][player-1] counts for player in col i
        self.diag = [0, 0]  # diag[player-1] counts for player in main diagonal
        self.anti_diag = [0, 0]  # anti_diag[player-1] counts for player in anti-diagonal
 
    def move(self, row: int, col: int, player: int) -> int:
        self.rows[row][player - 1] += 1
        self.cols[col][player - 1] += 1
        if row == col:
            self.diag[player - 1] += 1
        if row + col == self.n - 1:
            self.anti_diag[player - 1] += 1
        if (
            self.rows[row][player - 1] == self.n
            or self.cols[col][player - 1] == self.n
            or self.diag[player - 1] == self.n
            or self.anti_diag[player - 1] == self.n
        ):
            return player
        return 0
 

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure, adapting the data structures and syntax to the specific language. The underlying algorithmic approach remains the same.