Java Solution using 2 bits: beats 99.75%


  • 18
    // use the 1st bit to represent next generation 
    // use the 2nd bit to present current generation
    
     public class Solution {
            public void gameOfLife(int[][] board) {
                int rows=board.length;
                int cols=board[0].length;
                for(int i=0;i<rows;++i){
                    for(int j=0;j<cols;++j){
                        int neighbors = getNeighbour(board, i, j);
                        if(board[i][j]==1){
                            if(neighbors==2 || neighbors==3)
                                board[i][j]=3;
                        }else{
                            if(neighbors==3)
                                board[i][j]=2;
                        }
                    }
                }    
                for(int i=0;i<rows;++i){
                    for(int j=0;j<cols;++j){
                        board[i][j]>>=1;
                    }
                }
            }
            
            private int getNeighbour(int[][] board, int row, int col){
                int cnt=0;
                for(int i=row-1;i<=row+1;++i){
                    for(int j=col-1;j<=col+1;++j){
                        if(i>=0 && i<board.length && j>=0 && j<board[0].length){
                            cnt += board[i][j]&1;
                        }
                    }
                }
                cnt-=board[row][col]&1;
                return cnt;
            }
        }

  • 0
    P

    The number of upvotes speak volumes about your answer. But I observe that in your getNeighbour() function, you will end up adding the element along with the neighbourhood. Will it still fetch the correct results or am I missing something.


  • 0
    P

    If you are adding the element along with the neighbourhood elements , then the following condition will work.
    If the sum of all elements(including the element in consideration) is 3, then the element is always alive. If the sum is 4, then the element maintains its current state. In all the other cases, the element is dead.


  • 0

    You may miss this line :
    cnt-=board[row][col]&1;
    we deduct itself so the return value is number of neighbours


  • 0
    P

    Ah !! I missed that tiny minus. Sorry about that


  • 0
    C

    This is my first time to leave a message. Your solution is very smart and also easy to understand!! thx for sharing!!


  • 0
    M

    Thank you for posting . Your solution is crisp and easy to understand.
    However, I did get confused initially, it took me a while to understand the comments.

    // use the 1st bit to represent next generation
    // use the 2nd bit to present current generation

    Should it be reversed ??, usually we read bits from left to right. i.e.

    // use the 1st bit to represent current generation
    // use the 2nd bit to represent next generation

    Thank you again.


  • 0
    R

    Javascript version:

    var gameOfLife = function(board) {
        var rows = board.length;
            var cols = board[0].length;
            for(var i =0; i < rows; i++) {
                for(var j = 0; j < cols; ++j) {
                    var neighbors = getNeighbor(board, i , j);
                    if(board[i][j] == 1) {
                        if(neighbors == 2 || neighbors == 3)
                            board[i][j] = 3;
                    } else {
                        if(neighbors == 3)
                            board[i][j] = 2;
                    }
                }
            }
            for(var i = 0; i < rows; i++) {
                for(var j = 0; j < cols; j++) {
                    board[i][j]>>=1;
                }
            }
    };
    
    var getNeighbor = function(board, row, col) {
        var cnt = 0;
            for(var i = row - 1; i <= row + 1; ++i) {
                for(var j = col-1; j <= col +1; ++j){
                    if(i>=0 && i < board.length && j>=0 && j < board[0].length) {
                        cnt += board[i][j] & 1;
                    }
                }
            }
            cnt -= board[row][col]&1;
            return cnt;
        
    }
    

Log in to reply
 

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