Easiest JAVA solution with explanation


  • 523

    To solve it in place, we use 2 bits to store 2 states:

    [2nd bit, 1st bit] = [next state, current state]
    
    - 00  dead (next) <- dead (current)
    - 01  dead (next) <- live (current)  
    - 10  live (next) <- dead (current)  
    - 11  live (next) <- live (current) 
    
    • In the beginning, every cell is either 00 or 01.
    • Notice that 1st state is independent of 2nd state.
    • Imagine all cells are instantly changing from the 1st to the 2nd state, at the same time.
    • Let's count # of neighbors from 1st state and set 2nd state bit.
    • Since every 2nd state is by default dead, no need to consider transition 01 -> 00.
    • In the end, delete every cell's 1st state by doing >> 1.

    For each cell's 1st bit, check the 8 pixels around itself, and set the cell's 2nd bit.

    • Transition 01 -> 11: when board == 1 and lives >= 2 && lives <= 3.
    • Transition 00 -> 10: when board == 0 and lives == 3.

    To get the current state, simply do

    board[i][j] & 1
    

    To get the next state, simply do

    board[i][j] >> 1
    

    Hope this helps!

    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length, n = board[0].length;
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int lives = liveNeighbors(board, m, n, i, j);
    
                // In the beginning, every 2nd bit is 0;
                // So we only need to care about when will the 2nd bit become 1.
                if (board[i][j] == 1 && lives >= 2 && lives <= 3) {  
                    board[i][j] = 3; // Make the 2nd bit 1: 01 ---> 11
                }
                if (board[i][j] == 0 && lives == 3) {
                    board[i][j] = 2; // Make the 2nd bit 1: 00 ---> 10
                }
            }
        }
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;  // Get the 2nd state.
            }
        }
    }
    
    public int liveNeighbors(int[][] board, int m, int n, int i, int j) {
        int lives = 0;
        for (int x = Math.max(i - 1, 0); x <= Math.min(i + 1, m - 1); x++) {
            for (int y = Math.max(j - 1, 0); y <= Math.min(j + 1, n - 1); y++) {
                lives += board[x][y] & 1;
            }
        }
        lives -= board[i][j] & 1;
        return lives;
    }

  • 2

    Brilliant~~~~


  • 2
    C

    Thats an amazing Solution. Thumbs up!!


  • 2
    G

    yavinci, you always come up with great solutions!


  • 1

    Thanks! I like being straightforward : )


  • 0
    L

    Yavinci your solution is brilliant. But I have two questions regarding your solution.

    1. lives -= board[i][j] & 1; why did lives have to minus itself?
    2. Your solution traversed from top left to bottom right. But might the latter cell live/die affect the previous cell? Why shouldnt we consider this situation?

  • 5

    @Lazysheep.wang thanks for your question! (1) This is for conveniency. Notice that it's counting the 8 pixels around itself, not including itself. (2) Notice that bit0 is independent of bit1. Think about the board is changing from state1 "instantly" into state2. So we only retrieve the first state using board[i][j] & 1 and changing only the second state by changing 01 to 11 or 00 to 10. This is same as board[i][j] |= (1<<1).


  • 0
    L

    Thanks Yavinci for your explanation in detail. very helpful :)


  • 0
    F

    Thank U. awesome design, looks like an embedded programming tip.


  • 1

    @fxrcode, thanks! I was majored in EE.


  • 1
    C

    could not love more!


  • 0

    @amelia123 Cool. Makes sense! I've updated my answer.


  • 0
    M

    Great thought. Upvoted! Though I wish the code could be shorter :p


  • 0

    Thanks! You could delete my verbose comments haha.


  • 0
    N

    this is brilliant. I learn a lot from your code.


  • 0
    W

    Brilliant! The min max stuff and bit manipulation idea!


  • 0

    Well done, I use -1, 0, 1, 2 to represent 4 states. But your encoding looks better!


  • 1
    T

    This is in fact O(size of input) space. If there is only 1 or 0, then input should be bool [][] board, so it is equivalent to define vector<vector<bool>>


  • 0
    X

    Its awesome! use 2 bits to represent two states, (second state,first state). Its really ez to calculate the next state using ur idea!


  • 0
    Y

    so brilliant answer!


Log in to reply
 

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