348. Design Tic Tac Toe - cocoder39/coco39_LC GitHub Wiki

348. Design Tic-Tac-Toe

  • a straightforward approach: reserve state for every move eg board[][]. For each input row, col combination, check the corresponding entire row and column, diagonals
  • optimization: for each player, maintains rows[], cols[], diagonal1, diagonal2 to record its impact on each row, col, and diagonals
  • further optimization: 2 players share rows[], cols[], diagonal1, diagonal2. using +1/-1 to record impact from each player.
    • abs(self.rows[row]) == self.n iff a player places n keys on same row
    • abs(self.cols[col]) == self.n
    • abs(self.diagonal1) == self.n
    • abs(self.diagonal2) == self.n
class TicTacToe:

    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diagonal1 = 0
        self.diagonal2 = 0
        
    def move(self, row: int, col: int, player: int) -> int:
        delta = 1 if player == 1 else -1
        self.rows[row] += delta
        self.cols[col] += delta

        if row == col:
            self.diagonal1 += delta
        
        if row + col == self.n-1:
            self.diagonal2 += delta
        
        if abs(self.rows[row]) == self.n or abs(self.cols[col]) == self.n:
            return player
        
        if abs(self.diagonal1) == self.n or abs(self.diagonal2) == self.n:
            return player

        return 0

since a move() is guaranteed to be valid and is placed on an empty block, checking the number of marks of a related row/col/diagonal is enough to determine wining or not. Use +1 / -1 to distinguish marks from player 1 or player 2

time complexity is O(1) and space complexity is O(sz)

class TicTacToe {
public:
    /** Initialize your data structure here. */
    TicTacToe(int n) {
        sz = n;
        rows = vector<int>(sz);
        cols = vector<int>(sz);
    }
    
    /** 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. */
    int move(int row, int col, int player) {
        int inc = player == 1 ? 1 : -1;
        rows[row] += inc;
        cols[col] += inc;
        if (row == col)             diagonal += inc;
        if (row + col == sz - 1)    anti_diagonal += inc;
        
        return (abs(rows[row]) == sz || abs(cols[col]) == sz || 
            abs(diagonal) == sz || abs(anti_diagonal) == sz) ? 
            player : 0;
    }
private:
    int sz;
    vector<int> rows;
    vector<int> cols;
    int diagonal = 0;
    int anti_diagonal = 0;
};

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