Easiest JAVA solution with explanation

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

``````[2nd bit, 1st bit] = [next state, current state]

- 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;
}``````

• Brilliant~~~~

• Thats an amazing Solution. Thumbs up!!

• yavinci, you always come up with great solutions!

• Thanks! I like being straightforward : )

• 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?

• @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)`.

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

• @fxrcode, thanks! I was majored in EE.

• could not love more!

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

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

• Thanks! You could delete my verbose comments haha.

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

• Brilliant! The min max stuff and bit manipulation idea!

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

• 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>>

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

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