# Ac solution code

• The basic idea is updating one grid(board[i][j]) with the number of its liveNeighbors, according to the rules in the question.

The only trick is using two bits to store the grid's states in-place: 00, 01, 10, 11

``````1) low  bit: currState
2) high bit: nextState
``````

JAVA Code: O(nm) runtime; O(1) space*

``````public void gameOfLife(int[][] board) {
if (board == null || board.length == 0) return;
int n = board.length, m = board[0].length;
for(int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
updateGrid(board, i, j);// Update one grid(board[i][j]) with the number of its liveNeighbors
}
}
for(int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
board[i][j] >>= 1;// Update the current state with nextState (in high bit)
}
}
}
private void updateGrid(int[][]board, int i, int j) {// Update one grid(board[i][j]) with the number of its liveNeighbors
Point directions[] = {new Point(0, 1), new Point(0, -1), new Point(1, 0), new Point(-1, 0), new Point(1, 1), new Point(1, -1), new Point(-1, 1), new Point(-1, -1)};
int liveNeighbors = 0;
for (Point d : directions) {
if (i+d.x>=0 && i+d.x < board.length && j+d.y >=0 && j+d.y < board[0].length && (board[i+d.x][j+d.y] & 1) == 1) {// Check low bit
liveNeighbors++;
}
}
int nextState = board[i][j];
if (liveNeighbors < 2) nextState = 0; 		 // Any live cell with fewer than two live neighbors dies, as if caused by under-population.
else if (liveNeighbors == 3) nextState = 1;  // Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
else if (liveNeighbors > 3) nextState = 0;   // Any live cell with more than three live neighbors dies, as if by over-population..
board[i][j] |= nextState << 1;  		   	 // Set nextState to high bit
}``````

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