348. Design Tic-Tac-Toe

Naive n^2

T: move() : O(n^2)

S: O(n^2)

class TicTacToe {

    private int[][] board;
    private int n;
    public TicTacToe(int n) {
        board = new int[n][n];
        this.n = n;
    }
    
    public int move(int row, int col, int player) {

        board[row][col] = player == 1 ? 1 : -1;
       
        int diagnal = 0;
        int antiDiagnal = 0;
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            int rowResult = 0;
            int colResult = 0;

            for (int j = 0; j < n; j++) {
                rowResult += board[i][j];
                colResult += board[j][i];
            }
            diagnal += board[i][i];
            antiDiagnal += board[i][n-1-i];
            
            if (Math.abs(rowResult) == n) {
                return board[i][0] == 1 ? 1 : 2;
            }
            if (Math.abs(colResult) == n) {
                return board[0][i] == 1 ? 1 : 2;
            }
        }
        if (Math.abs(diagnal) == n) {
            return board[0][0] == 1 ? 1 : 2;
        }
        if (Math.abs(antiDiagnal) == n) {
            return board[0][n-1] == 1 ? 1 : 2;
        }

        return 0;
    }
}

/**
00 1 02 
 1  2 
20  22

00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33





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

O(1) solution

其實我們關心的是整 row, or 整 col, 每次新的 move 都加在之前結果上就可以決定是不是 win 了

所以紀錄整 row 的總和, 整個 col 的總和即可, 不用每次都整個重算

T: move(): O(1)

S: O(n)

class TicTacToe {

    private int[] rows;
    private int[] cols;
    int diagnal = 0;
    int antiDiagnal = 0;
    
    private int n;
    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
        this.n = n;
    }
    
    public int move(int row, int col, int player) {

        int add = player == 1 ? 1 : -1;
        
        rows[row] += add;
        cols[col] += add;
        
        if (row == col) {
            diagnal += add;
        }
        if (col == n - row - 1) { // antiDiagnal, or if (row+col == n-1) is also ok
            antiDiagnal += add;
        }
        if (Math.abs(rows[row]) == n ||
            Math.abs(cols[col]) == n ||
            Math.abs(diagnal) == n ||
            Math.abs(antiDiagnal) == n) {
            
            return player;
        }

        return 0;
    }
}

/**

00 01 02
10 11 12
20 21 22

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