Java in-place O(mn) solution


  • 6

    Use bit operation to store new value in higher bit.

    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = getNeighbors(board, i, j, m , n);
                if (count == 3 || board[i][j] + count == 3) {
                    board[i][j] ^= 2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = board[i][j] >> 1;
            }
        }
    }
    
    private int getNeighbors(int[][] board, int i, int j, int m, int n) {
        int result = 0;
        for (int x = Math.max(i-1, 0); x < Math.min(i+2, m); x++) {
            for (int y = Math.max(j-1, 0); y < Math.min(j+2, n); y++) {
                result += (board[x][y] & 1);
            }
        }
        return result - (board[i][j] & 1);
    }

  • 1

    I think this solution is the very readable. Thanks!


  • 0
    T

    I think that XOR in board[i][j] ^= 2 is uncalled for, is there any setup when the second from right bit is 1 at that point? For simplicity I would say board[i][j] |= 0b10 is enough.


Log in to reply
 

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