Game of Life
Medium · Arrays & Hashing · Explanation and code example
Store Old and New Cell States in Bits
How it works
Encode the old generation in the low bit and the next generation in the second bit. Neighbor counts always read the low bit, so earlier updates cannot contaminate later counts. Shift every cell right once all next states have been computed.
Steps
- Count low-bit ones in each surrounding 3×3 region.
- Set the second bit when the cell survives or is born.
- Shift all cells right to expose the next generation.
Complexity
- Time: O(rows × columns).
- Space: O(1).
Things to watch for
- The count includes the cell itself, so a live cell survives at counts three or four.
- Read neighbor old states with & 1.
- Do not replace the old state before all cells have been examined.
Python code example
class Solution:
def gameOfLife(self, board: list[list[int]]) -> None:
m = len(board)
n = len(board[0])
for i in range(m):
for j in range(n):
ones = 0
for x in range(max(0, i - 1), min(m, i + 2)):
for y in range(max(0, j - 1), min(n, j + 2)):
ones += board[x][y] & 1
# Any live cell with two or three live neighbors lives on to the next
# generation.
if board[i][j] == 1 and (ones == 3 or ones == 4):
board[i][j] |= 0b10
# Any dead cell with exactly three live neighbors becomes a live cell,
# as if by reproduction.
if board[i][j] == 0 and ones == 3:
board[i][j] |= 0b10
for i in range(m):
for j in range(n):
board[i][j] >>= 1
C++ code example
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
const int m = board.size();
const int n = board[0].size();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
int ones = 0;
for (int x = max(0, i - 1); x < min(m, i + 2); ++x)
for (int y = max(0, j - 1); y < min(n, j + 2); ++y)
ones += board[x][y] & 1;
// Any live cell with two or three live neighbors lives on to the next
// generation.
if (board[i][j] == 1 && (ones == 3 || ones == 4))
board[i][j] |= 0b10;
// Any dead cell with exactly three live neighbors becomes a live cell,
// as if by reproduction.
if (board[i][j] == 0 && ones == 3)
board[i][j] |= 0b10;
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
board[i][j] >>= 1;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.