Leetcode Problem 348 Design Tic-Tac-Toe.txt

348. Design Tic-Tac-Toe
Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

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

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|
Follow up:
Could you do better than O(n2) per move() operation?





Hint to solve: Use +1 for player 1 and -1 for player 2
Make separate array for rows and cols
Track diagonal and antidiagonal into an integer value.

Use dynamic programming for same row add the move value to it
Use dynamic programming for same col add the move value to it.
Check condition for diagonal and antidiagonal and update the value

Any player would win only if the 
    current row cell value reaches the size of grid
    current col cell value reaches the size of grid
    diagonal reaches the size of grid
    antidiagonal reaches the size of grid
    

class TicTacToe:

    def __init__(self, n: int):
        """
        Initialize your data structure here.
        """
        self.size = n
        self.rows = [0 for _ in range(n)]
        self.cols = [0 for _ in range(n)]
        self.diagonal = 0
        self.antiDiagonal = 0
        self.MoveValue = 0
        

    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.
        """
        
        MoveValue = 1 if player == 1 else -1
        
        self.rows[row] += MoveValue
        self.cols[col] += MoveValue
        
        if row == col:
            self.diagonal += MoveValue
        
        if col == (len(self.cols) - row - 1):
            self.antiDiagonal += MoveValue
        
        #print(F'rows:{self.rows} cols:{self.cols} diagonal: {self.diagonal} antidiagonal: {self.antiDiagonal}')
        
        if (abs(self.rows[row]) == self.size
           or abs(self.cols[col]) == self.size
           or abs(self.diagonal) == self.size
           or abs(self.antiDiagonal) == self.size):
            return player
        
        
        return 0