Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/348.html

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves are allowed.
  3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

  • TicTacToe(int n) Initializes the object the size of the board n.
  • int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return
    • 0 if there is no winner after the move,
    • 1 if player 1 is the winner after the move, or
    • 2 if player 2 is the winner after the move.

 

Example 1:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

Explanation
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is "X" and player 2 is "O" in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

 

Constraints:

  • 2 <= n <= 100
  • player is 1 or 2.
  • 0 <= row, col < n
  • (row, col) are unique for each different call to move.
  • At most n2 calls will be made to move.

 

Follow-up: Could you do better than O(n2) per move() operation?

Algorithm

The provided Python code defines a class TicTacToe that simulates a game of tic-tac-toe with a board of size n x n. The class is designed to efficiently check if a move by a player results in a win. Here’s a breakdown of the code:

Initialization (__init__ method)

  • The constructor initializes four attributes:
    • self.rows and self.cols: Arrays of length n that track the cumulative scores of rows and columns, respectively. A positive score favors one player, while a negative score favors the other.
    • self.diag and self.antiDiag: Variables to track the scores of the main diagonal (top-left to bottom-right) and the anti-diagonal (top-right to bottom-left), respectively.
    • self.n: Stores the size of the board.

The move Method

  • This method is dynamically defined within the __init__ method and is attached to the class instance. It’s used to make a move on the board and checks if this move wins the game.
  • Parameters:
    • row and col: Indicate the position of the move.
    • player: Indicates the player making the move. player is either 1 or 2.
  • delta: A value calculated based on the player making the move. If player is 1, delta is 1; if player is 2, delta is -1. This approach allows using a single set of counters for both players, where one player increases the counters and the other decreases them.
  • The method updates the rows, cols, diag, and antiDiag counters based on the move. For the diagonal counters, it adds delta only if the move is on the respective diagonal.
  • After updating the counters, the method checks if any of them equals n * delta or -n * delta (depending on the player). Such a value indicates that a player has filled an entire row, column, or diagonal, thus winning the game.
  • The method returns the player number if they win with this move or 0 if the game continues.

Key Points

  • The design efficiently checks for a win condition without iterating through the board after every move, leveraging arithmetic to track the state of the game.
  • It abstracts the game’s state into numerical counters, allowing for quick win condition checks.
  • This implementation supports only two players and assumes correct input for each move.

On python’s and operation

In Python, the expression 1+1==2 and delta involves both a comparison operation and a logical AND operation. When delta = -1, here’s how Python evaluates this expression:

  1. Comparison: The expression starts with 1+1==2. Python evaluates 1+1 to get 2, and then checks if 2 is equal to 2. Since this is true, the comparison 1+1==2 evaluates to True.

  2. Logical AND: The and operator in Python performs a logical AND operation. It evaluates to True if both sides of the and are truthy, and False otherwise. A truthy value is any value that is not considered False or empty in a Boolean context. Non-zero numbers, including negative numbers, are considered truthy.

  3. Evaluation with delta: Since delta = -1, the right side of the and is -1. In Python, -1 is considered a truthy value because it’s not zero.

Putting it all together, 1+1==2 evaluates to True, and since -1 is truthy, the whole expression 1+1==2 and delta evaluates to the value of delta because of how the and operator works:

  • if the first value is True, it returns the second value. This behavior is part of Python’s short-circuit evaluation.
  • The and operator returns the first falsy value it encounters or the last value if none are falsy. Since the comparison is True, the and operator returns delta.

Therefore, when delta = -1, the expression 1+1==2 and delta evaluates to -1.

Code

  • public class Design_Tic_Tac_Toe {
    int[][] matrix;

    /**
     * Initialize your data structure here.
     */
    public Design_Tic_Tac_Toe(int n) {
        matrix = new int[n][n];
    }

    /**
     * Player {player} makes a move at ({row}, {col}).
     *
     * @param row    The row of the board.
     * @param col    The column of the board.
     * @param player The player, can be either 1 or 2.
     * @return The current winning condition, can be either:
     * 0: No one wins.
     * 1: Player 1 wins.
     * 2: Player 2 wins.
     */
    public int move(int row, int col, int player) {

        int[] rows = new int[3];
        int[] cols = new int[3];
        int[] diag = new int[2];

        int val = player == 1 ? 1: -1;

        rows[row] += val; // assumption: valid input, no override for same location
        cols[col] += val;

        if (row == col) {
            diag[0] += val;
        }
        if (row + col == 2) {
            diag[1] += val;
        }

        if (Math.abs(rows[row]) == 3
            || Math.abs(cols[col]) == 3
            || Math.abs(diag[0]) == 3
            || Math.abs(diag[1]) == 3) {
            return player;
        }

        return 0;
    }

    public int move_naive_solution(int row, int col, int player) {

        matrix[row][col] = player;

        //check row
        boolean win = true;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[row][i] != player) {
                win = false;
                break;
            }
        }
        if (win) return player;
        //check column
        win = true;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][col] != player) {
                win = false;
                break;
            }
        }
        if (win) return player;
        //check back diagonal
        win = true;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][i] != player) {
                win = false;
                break;
            }
        }
        if (win) return player;
        //check forward diagonal
        win = true;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][matrix.length - i - 1] != player) {
                win = false;
                break;
            }
        }
        if (win) return player;
        return 0;
    }
}

############

class TicTacToe {
    private int n;
    private int[][] counter;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        counter = new int[2][(n << 1) + 2];
        this.n = n;
    }

    /**
       Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins.
     */
    public int move(int row, int col, int player) {
        counter[player - 1][row] += 1;
        counter[player - 1][col + n] += 1;
        if (row == col) {
            counter[player - 1][n << 1] += 1;
        }
        if (row + col == n - 1) {
            counter[player - 1][(n << 1) + 1] += 1;
        }
        if (counter[player - 1][row] == n || counter[player - 1][col + n] == n
            || counter[player - 1][n << 1] == n || counter[player - 1][(n << 1) + 1] == n) {
            return player;
        }
        return 0;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

  • // OJ: https://leetcode.com/problems/design-tic-tac-toe/
// Time: O(N)
// Space: O(N^2)
class TicTacToe {
private:
    vector<vector<int>> board;
    int n;
    int status(int row, int col) {
        int p = board[row][col];
        bool win = true;
        for (int i = 0; i < n && win; ++i) {
            if (board[row][i] != p) win = false;
        }
        if (win) return p;
        win = true;
        for (int i = 0; i < n && win; ++i) {
            if (board[i][col] != p) win = false;
        }
        if (win) return p;
        if (row == col) {
            win = true;
            for (int i = 0; i < n && win; ++i) {
                if (board[i][i] != p) win = false;
            }
            if (win) return p;
        }
        if (row + col == n - 1) {
            win = true;
            for (int i = 0; i < n && win; ++i) {
                if (board[i][n - 1 - i] != p) win = false;
            }
            if (win) return p;
        }
        return 0;
    }
public:
    TicTacToe(int n) : n(n) {
        board = vector<vector<int>>(n, vector<int>(n));
    }
    int move(int row, int col, int player) {
        board[row][col] = player;
        return status(row, col);
    }
};

  • '''
>>> delta = 1
>>> 1+1==2
True
>>> 1+1==2 and delta
1
>>>
>>>
>>> delta = -1
>>> 1+1==2 and delta
-1
>>>
>>> delta = -100
>>> 1+1==2 and delta
-100
>>>
>>> delta = -100
>>> 1+1==99 and delta
False
>>>
'''

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

    def move(row, col, player):
      delta = 3 - player * 2
      self.rows[row] += delta
      self.cols[col] += delta
      self.diag += (row == col and delta)
      self.antiDiag += (row + col == self.n - 1 and delta)
      if delta * self.n in [self.rows[row], self.cols[col], self.diag, self.antiDiag]:
        return player
      return 0

    self.move = move

# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

############

class TicTacToe:
    def __init__(self, n: int):
        """
        Initialize your data structure here.
        """
        self.n = n
        self.counter = [[0] * ((n << 1) + 2) for _ in range(2)]

    def move(self, row: int, col: int, player: int) -> int:
        """
        Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins.
        """
        n = self.n
        self.counter[player - 1][row] += 1
        self.counter[player - 1][col + n] += 1
        if row == col:
            self.counter[player - 1][n << 1] += 1
        if row + col == n - 1:
            self.counter[player - 1][(n << 1) + 1] += 1
        if (
            self.counter[player - 1][row] == n # taking full row
            or self.counter[player - 1][col + n] == n # full col
            or self.counter[player - 1][n << 1] == n # full diag
            or self.counter[player - 1][(n << 1) + 1] == n # full anti diag
        ):
            return player
        return 0

# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)


  • type TicTacToe struct {
	n   int
	cnt [][]int
}

func Constructor(n int) TicTacToe {
	cnt := make([][]int, 2)
	for i := range cnt {
		cnt[i] = make([]int, (n<<1)+2)
	}
	return TicTacToe{n, cnt}
}

func (this *TicTacToe) Move(row int, col int, player int) int {
	cur := this.cnt[player-1]
	cur[row]++
	cur[this.n+col]++
	if row == col {
		cur[this.n<<1]++
	}
	if row+col == this.n-1 {
		cur[this.n<<1|1]++
	}
	if cur[row] == this.n || cur[this.n+col] == this.n || cur[this.n<<1] == this.n || cur[this.n<<1|1] == this.n {
		return player
	}
	return 0
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Move(row,col,player);
 */

  • class TicTacToe {
    private n: number;
    private cnt: number[][];

    constructor(n: number) {
        this.n = n;
        this.cnt = [Array((n << 1) + 2).fill(0), Array((n << 1) + 2).fill(0)];
    }

    move(row: number, col: number, player: number): number {
        const cur = this.cnt[player - 1];
        cur[row]++;
        cur[this.n + col]++;
        if (row === col) {
            cur[this.n << 1]++;
        }
        if (row + col === this.n - 1) {
            cur[(this.n << 1) | 1]++;
        }
        if (
            cur[row] === this.n ||
            cur[this.n + col] === this.n ||
            cur[this.n << 1] === this.n ||
            cur[(this.n << 1) | 1] === this.n
        ) {
            return player;
        }
        return 0;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * var obj = new TicTacToe(n)
 * var param_1 = obj.move(row,col,player)
 */

All Problems

All Solutions