Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/348.html
Assume the following rules are for the tictactoe game on an n x n
board between two players:
 A move is guaranteed to be valid and is placed on an empty block.
 Once a winning condition is reached, no more moves are allowed.
 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 boardn
.int move(int row, int col, int player)
Indicates that the player with idplayer
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. Return0
if there is no winner after the move,1
if player 1 is the winner after the move, or2
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 OO  // Player 2 makes a move at (1, 0). X X ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) X O OO  // Player 1 makes a move at (2, 1). XXX
Constraints:
2 <= n <= 100
 player is
1
or2
. 0 <= row, col < n
(row, col)
are unique for each different call tomove
. At most
n^{2}
calls will be made tomove
.
Followup: Could you do better than O(n^{2})
per move()
operation?
Algorithm
The provided Python code defines a class TicTacToe
that simulates a game of tictactoe 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
andself.cols
: Arrays of lengthn
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
andself.antiDiag
: Variables to track the scores of the main diagonal (topleft to bottomright) and the antidiagonal (topright to bottomleft), 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
andcol
: 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. Ifplayer
is 1,delta
is 1; ifplayer
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
, andantiDiag
counters based on the move. For the diagonal counters, it addsdelta
only if the move is on the respective diagonal.  After updating the counters, the method checks if any of them equals
n * delta
orn * 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:

Comparison: The expression starts with
1+1==2
. Python evaluates1+1
to get2
, and then checks if2
is equal to2
. Since this is true, the comparison1+1==2
evaluates toTrue
. 
Logical AND: The
and
operator in Python performs a logical AND operation. It evaluates to True if both sides of theand
are truthy, and False otherwise. A truthy value is any value that is not consideredFalse
or empty in a Boolean context. Nonzero numbers, including negative numbers, are considered truthy. 
Evaluation with
delta
: Sincedelta = 1
, the right side of theand
is1
. 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 shortcircuit evaluation.  The
and
operator returns the first falsy value it encounters or the last value if none are falsy. Since the comparison isTrue
, theand
operator returnsdelta
.
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/designtictactoe/ // 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)