Java in place o(n*m)


  • 0
    A
    public void gameOfLife(int[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                int nbLive = countNeighborsAlive(board, i, j);
                if (board[i][j] == 0 || board[i][j] >= 20) {
                    board[i][j] = nbLive == 3 ? 21 : 20;
                } else {
                    board[i][j] = (nbLive < 2 || nbLive > 3) ? 10 : 11;
                }
            }
        }
        // restore last cell to 0 or 1
        board[board.length-1][board[0].length-1] = board[board.length-1][board[0].length-1] % 2;
    }
    
    public int countNeighborsAlive(int[][] board, int i, int j) {
        int inc = 0;
    
        boolean i_ = i == board.length - 1;
        boolean j_ = j == board[0].length - 1;
        boolean _i = i == 0;
        boolean _j = j == 0;
    
        // count alive cells
        if (!i_ && !j_) inc += getVal(board[i+1][j+1]);
        if (!i_)        inc += getVal(board[i+1][j  ]);
        if (!i_ && !_j) inc += getVal(board[i+1][j-1]);
        if (!j_)        inc += getVal(board[i  ][j+1]);
        if (!_j)        inc += getVal(board[i  ][j-1]);
        if (!_i && !j_) inc += getVal(board[i-1][j+1]);
        if (!_i)        inc += getVal(board[i-1][j  ]);
        if (!_i && !_j) inc += getVal(board[i-1][j-1]);
    
        // restore cells to 0 or 1
        if (!_i && !_j) board[i-1][j-1] = board[i-1][j-1] % 2;
        if (j_ && !_i) board[i-1][j] = board[i-1][j] % 2;
        if (i_ && !_j) board[i][j-1] = board[i][j-1] % 2;
    
        return inc;
    }
    
    private int getVal(int i) {
        return (i == 1 || i == 10 || i == 11) ? 1 : 0;
    }

Log in to reply
 

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