Problem Description

You are tasked with designing a Tic-Tac-Toe game played by two players on an n x n grid. The game should support two operations:

• move(row, col, player): Places the player's mark (1 or 2) at the given row and col position.
• After each move, determine if that move caused the player to win the game. A player wins if they fill an entire row, column, or diagonal with their mark.

• Only one move is made at a time per player.
• The board size n is provided at initialization and does not change.
• Moves are valid (no overwriting of marks).
• Return 0 if no one wins after a move, or the player number (1 or 2) who wins.

Thought Process

The naive way to check for a win after each move would be to scan the entire row, column, and both diagonals for every move. This works, but it is inefficient, especially as the board size increases, requiring O(n) time per move.
To improve, we can keep track of the counts of each player's marks in each row, column, and diagonal. If at any point, a player's count for a row, column, or diagonal reaches n, they win. This approach lets us check for a win in constant time after each move, which is much more efficient.

Solution Approach

We'll design a TicTacToe class with the following features:

• Initialization: Store the board size n. For each player, maintain arrays for row and column counts, and integers for both diagonals.
• Move operation:
  • On each move, increment the appropriate row and column count for the current player.
  • If the move is on the main diagonal (row == col), increment the diagonal count.
  • If the move is on the anti-diagonal (row + col == n - 1), increment the anti-diagonal count.
  • If any of these counts reaches n (for player 1) or -n (for player 2, if using +1/-1 approach), declare that player as the winner.
• Why use +1/-1? For a more concise implementation, we can use +1 for player 1 and -1 for player 2, updating the same arrays and checking for n or -n.
• Efficiency: All operations are O(1) per move.

Example Walkthrough

Consider a 3x3 board. Player 1 and Player 2 take turns:

• Player 1: move(0, 0, 1) — row 0, col 0, main diagonal updated.
• Player 2: move(0, 2, 2) — row 0, col 2, anti-diagonal updated.
• Player 1: move(1, 1, 1) — row 1, col 1, both diagonals updated.
• Player 2: move(1, 2, 2) — row 1, col 2.
• Player 1: move(2, 2, 1) — row 2, col 2, main diagonal updated.

Time and Space Complexity

Brute-force:

• Time: O(n) per move, as you would scan the whole row, column, and diagonals.
• Space: O(n^2) if you store the entire board.

• Time: O(1) per move, since we only update and check counters.
• Space: O(n) for row and column counters, plus O(1) for diagonals.

Summary

By tracking row, column, and diagonal counts for each player, we can determine a win in constant time after each move. This approach is much more scalable and elegant than checking the board after every move. The use of counters and the clever +1/-1 trick makes the solution concise and efficient, especially for large boards.

Code Implementation

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> int:
        to_add = 1 if player == 1 else -1

        self.rows[row] += to_add
        self.cols[col] += to_add

        if row == col:
            self.diag += to_add
        if row + col == self.n - 1:
            self.anti_diag += to_add

        if (abs(self.rows[row]) == self.n or
            abs(self.cols[col]) == self.n or
            abs(self.diag) == self.n or
            abs(self.anti_diag) == self.n):
            return player
        return 0
      

class TicTacToe {
public:
    vector<int> rows, cols;
    int diag, anti_diag, n;
    TicTacToe(int n) : rows(n), cols(n), diag(0), anti_diag(0), n(n) {}
    
    int move(int row, int col, int player) {
        int toAdd = player == 1 ? 1 : -1;
        rows[row] += toAdd;
        cols[col] += toAdd;
        if (row == col) diag += toAdd;
        if (row + col == n - 1) anti_diag += toAdd;
        if (abs(rows[row]) == n || abs(cols[col]) == n ||
            abs(diag) == n || abs(anti_diag) == n)
            return player;
        return 0;
    }
};
      

class TicTacToe {
    private int[] rows, cols;
    private int diag, antiDiag, n;
    public TicTacToe(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
        this.diag = 0;
        this.antiDiag = 0;
    }
    
    public int move(int row, int col, int player) {
        int toAdd = player == 1 ? 1 : -1;
        rows[row] += toAdd;
        cols[col] += toAdd;
        if (row == col) diag += toAdd;
        if (row + col == n - 1) antiDiag += toAdd;
        if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n ||
            Math.abs(diag) == n || Math.abs(antiDiag) == n)
            return player;
        return 0;
    }
}
      

class TicTacToe {
    constructor(n) {
        this.n = n;
        this.rows = Array(n).fill(0);
        this.cols = Array(n).fill(0);
        this.diag = 0;
        this.antiDiag = 0;
    }
    
    move(row, col, player) {
        const toAdd = player === 1 ? 1 : -1;
        this.rows[row] += toAdd;
        this.cols[col] += toAdd;
        if (row === col) this.diag += toAdd;
        if (row + col === this.n - 1) this.antiDiag += toAdd;
        if (Math.abs(this.rows[row]) === this.n ||
            Math.abs(this.cols[col]) === this.n ||
            Math.abs(this.diag) === this.n ||
            Math.abs(this.antiDiag) === this.n)
            return player;
        return 0;
    }
}