Solution for Tic-Tac-Toe Runtime of Move function: O(1)


  • 0
    M

    The runtime of the move function of this solution is constant. It does not depend on the value of n.
    The concept of the solution is fairly simple - Each move only affects only a specific column/row or two diagonal for that player only. If you know the total move count of that player for those four places ( that row, that column, and the two diagonals) then you can come to a conclusion that whether that player wins or not.

    class TicTacToe {
        int[][] hstatus; //contains the total move count for each player for each row.
        int[][] vstatus; //contains the total move count for each player for each column.
        int[][] dstatus; //contains the total move count for each player for both diagonal.
        int n = 0; //size of the board.
    
        /** Initialize your data structure here. */
        public TicTacToe(int n) {
            this.n = n;
            hstatus= new int[2][n];
            vstatus= new int[2][n];
            dstatus = new int[2][2];
        }
    
        /** 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) {   
            // update the count for the row which is effected by the move
            hstatus[player-1][row]++;
            if(hstatus[player-1][row] == n) { //if entire row contains the player's moves then he wins
                return player;
            }
    
            // update the count for the vertical column which is effected by the move
            vstatus[player-1][col]++;
            if(vstatus[player-1][col] == n) {  //if entire column contains players move then he wins
                return player;
            }
            if(row == col) {   // if this is on top-left to bottom-right diagonal position.
                dstatus[player-1][0]++;
                if(dstatus[player-1][0] == n) {
                    return player;
                }
            }
    
            if(row == n-col-1) { // if this is on bottom-left to top-right diagonal position.
                dstatus[player-1][1]++;
                if(dstatus[player-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);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.