# C++ O(1) space, O(mn) time

• Since the board has ints but only the 1-bit is used, I use the 2-bit to store the new state. At the end, replace the old state with the new state by shifting all values one bit to the right.

``````void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = m ? board[0].size() : 0;
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
int count = 0;
for (int I=max(i-1, 0); I<min(i+2, m); ++I)
for (int J=max(j-1, 0); J<min(j+2, n); ++J)
count += board[I][J] & 1;
if (count == 3 || count - board[i][j] == 3)
board[i][j] |= 2;
}
}
for (int i=0; i<m; ++i)
for (int j=0; j<n; ++j)
board[i][j] >>= 1;
}
``````

Note that the above `count` counts the live ones among a cell's neighbors and the cell itself. Starting with `int count = -board[i][j]` counts only the live neighbors and allows the neat

``````if ((count | board[i][j]) == 3)
``````

test. Thanks to aileenbai for showing that one in the comments.

• Great code! Well, you include the cell itself when counting the 8 neighbors. At first I did not notice it and had been confused for some time :-)

• Hi Stefan, your algorithm is perfect as always! It took me a little while to understand the code`if (count == 3 || count - board[i][j] == 3)` I thought it should be `if (count == 3 || count + board[i][j] == 3)`. Then I realized that you also checked the cell itself. Good job!!!

• Haha, I have also been confused by that part for some time...

• Just in case you like confusion, replace

``````if (count == 3 || count - board[i][j] == 3)
board[i][j] |= 2;
``````

with

``````board[i][j] |= (2*count - board[i][j]) % 13 % 8 / 5 * 2;
``````

:-)

• Maybe I should have initialized `count = -board[i][j]` to make it work "as expected".
But it would be a bit duplicated code and I don't like that :-P

• Oh, I got totally confused...

• great job!
I had never thought of using extra bits...
and `if (count == 3 || count - board[i][j] == 3)` is also very refined,
although I think it is a bit something as the two conditions contain one same situation...

• I got totally confused too...

• nice code, the idea was in my mind but hard to come up with an implementation initially.
it may more clear to write
if (board[i][j] == 1 && (count == 2 || count ==3) || board[i][j] == 0 && count == 3)
as following the description. but longer.

• I have a shorter one :)

``````if ((count | board[i][j]) == 3)
``````

Oh I did not count the cell itself

• Wow, how could I miss that?! Thanks, I included it in my question now.

• This post is deleted!

• Because of the `& 1`.

• very clever . Thanks for sharing.

• This post is deleted!

• Maybe small change makes it more easy to understand.

``````class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int m=board.size(), n=m?board[0].size():0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
int count=0;
for(int ss=max(i-1, 0); ss<min(i+2, m); ss++){
for(int tt=max(j-1, 0); tt<min(j+2, n); tt++){
count+=board[ss][tt]&1;
}
}
count-=board[i][j];

if(count==3 || (board[i][j]&&count==2))
board[i][j]|=2;
}
}

for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
board[i][j]>>=1;
}
};``````

• This post is deleted!

• use the 2-bit to store the new state. So clever!

• Amazing! Just curious time complexity O(m*n) - shall we count the 8 visits caused by 8 neighbor count processes, especially for those cells are not on the edge?

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