Problem Statement
According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously.
Given the current state of the board, update the board to reflect its next state.
Note that you do not need to return anything.
Examples
Example 1:
Input: board = [
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
Output: [
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]Example 2:
Input: board = [
[1,1],
[1,0]
]
Output: [
[1,1],
[1,1]
]Different Approaches
1️⃣ Brute Force Approach (Using extra space)
Intuition:
We would make use of extra matrix copy of the original one, where we would update the state changes, after complete traversal of the original matrix. We copy the copied matrix to original one.
Code:
class Solution {
public:
// Direction vectors for 8 neighbors (N, E, S, W, NE, NW, SE, SW)
int dimX[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dimY[8] = {0, 1, 0, -1, 1, -1, 1, -1};
// Helper to check if cell is within grid bounds
bool isValid(int row, int col, int n, int m) {
return row >= 0 && row < n && col >= 0 && col < m;
}
void gameOfLife(vector<vector<int>>& board) {
int n = board.size(); // Number of rows
int m = board[0].size(); // Number of columns
// Make a copy of the original board to preserve original states
vector<vector<int>> copy = board;
// Step 1: Traverse each cell and apply the rules
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
int liveCount = 0;
// Step 2: Count live neighbors using 8 directions
for (int i = 0; i < 8; i++) {
int newRow = row + dimX[i];
int newCol = col + dimY[i];
if (isValid(newRow, newCol, n, m)) {
if (board[newRow][newCol] == 1)
liveCount++;
}
}
// Step 3: Apply rules of the Game of Life
if (board[row][col] == 1) {
// Live cell with <2 or >3 live neighbors dies
if (liveCount < 2 || liveCount > 3)
copy[row][col] = 0;
else
copy[row][col] = 1; // Survives
} else {
// Dead cell with exactly 3 live neighbors becomes alive
if (liveCount == 3)
copy[row][col] = 1;
else
copy[row][col] = 0; // Remains dead
}
}
}
// Step 4: Copy back updated state to original board
board = copy;
}
};
Complexity Analysis:
- Time Complexity:
O(n * m), wherenis the number of rows, whilemis the number of columns.O(n * m): For traversing to the entire matrix- For each cell, we check 8 neighbors → constant time
O(1)(since 8 is a fixed number). - So:
O(8 * n * m)=O(n * m)(constant factors are dropped in Big-O).
- For each cell, we check 8 neighbors → constant time
O(n * m): To copy values from the duplicate matrix to original one.- Final Complexity:
O(n * m) + O(n * m)=2 * O(n * m), (again constant factor are dropped) →O(n * m)
- Space Complexity:
O(n * m)- As we maintain a duplicate matrix to store the next state.
2️⃣ Optimal Approach (Encoding)
Intuition:
We use state encoding to store both previous and next state in the same matrix:
| Current State | Next State | Encoding |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 1 | 0 | 2 (Live → Dead) |
| 0 | 1 | 3 (Dead → Live) |
Later, we will decode:
- 2 → change to 0
- 3 → change to 1
Code:
class Solution {
public:
// Direction vectors to access 8 neighbors: top-left, top, top-right, left, right, bottom-left, bottom, bottom-right
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// Function to check if a cell (x, y) is inside the board boundaries
bool isValid(int x, int y, int n, int m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void gameOfLife(vector<vector<int>>& board) {
int n = board.size(); // number of rows
int m = board[0].size(); // number of columns
/*
Step 1:
Traverse the board and apply temporary encoded states to mark transitions:
- 1 → 0 (Live to Dead): mark as 2
- 0 → 1 (Dead to Live): mark as 3
*/
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
int liveNeighbors = 0; // Count of live neighbors around cell (row, col)
// Check all 8 possible neighbors
for (int dir = 0; dir < 8; dir++) {
int newRow = row + dx[dir];
int newCol = col + dy[dir];
// If neighbor cell is valid and was originally alive (1 or 2), count it
if (isValid(newRow, newCol, n, m)) {
if (board[newRow][newCol] == 1 || board[newRow][newCol] == 2)
liveNeighbors++;
}
}
// Apply Game of Life rules using temporary encodings
if (board[row][col] == 1) {
// Rule 1 or 3: Live cell dies if <2 or >3 live neighbors
if (liveNeighbors < 2 || liveNeighbors > 3) {
board[row][col] = 2; // mark as live to dead
}
// Rule 2: Live cell with 2 or 3 neighbors stays alive → do nothing
} else {
// Rule 4: Dead cell becomes alive if it has exactly 3 live neighbors
if (liveNeighbors == 3) {
board[row][col] = 3; // mark as dead to live
}
}
}
}
/*
Step 2:
Finalize the board by converting temporary states to final states:
- 2 → 0 (was live, now dead)
- 3 → 1 (was dead, now live)
*/
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
if (board[row][col] == 2)
board[row][col] = 0;
else if (board[row][col] == 3)
board[row][col] = 1;
}
}
}
};
Complexity Analysis:
- Time Complexity:
O(n * m) - Space Complexity:
O(1)
3️⃣ Bitwise Encoding Trick
Each cell can be encoded with 2 bits:
00 → dead → stays dead
01 → live → becomes dead
10 → dead → becomes live
11 → live → stays liveThe LSB (last bit, cell & 1) = current state
The 2nd bit = next state
Intuition:
When iterating:
- Check the current state using board[row][col] & 1
- Set the next state using bit manipulation:
- board[row][col] |= 2 → sets the second bit (next state to live)
Code:
class Solution {
public:
// Direction vectors to traverse the 8 neighboring cells
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
// Check if a given (x, y) coordinate is inside the grid
bool isValid(int x, int y, int n, int m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void gameOfLife(vector<vector<int>>& board) {
int n = board.size(); // Number of rows
int m = board[0].size(); // Number of columns
// STEP 1: Traverse the grid to compute the next state for each cell
for (int row = 0; row < n; ++row) {
for (int col = 0; col < m; ++col) {
int liveNeighbors = 0;
// Count how many live neighbors the current cell has
for (int dir = 0; dir < 8; ++dir) {
int nx = row + dx[dir];
int ny = col + dy[dir];
// Check bounds and count only if neighbor is currently alive
if (isValid(nx, ny, n, m) && (board[nx][ny] & 1)) {
liveNeighbors++;
}
}
// STEP 2: Use second bit to encode the next state
// Current state is in the LSB (bit 0), next state will go into bit 1
if (board[row][col] & 1) {
// Current cell is alive
if (liveNeighbors == 2 || liveNeighbors == 3) {
// Cell remains alive — set second bit to 1
board[row][col] |= 2;
}
// Else: Cell dies — second bit remains 0 (implicitly)
} else {
// Current cell is dead
if (liveNeighbors == 3) {
// Cell becomes alive — set second bit to 1
board[row][col] |= 2;
}
// Else: Cell stays dead — second bit remains 0
}
}
}
// STEP 3: Finalize the grid by shifting bits to get the next state
for (int row = 0; row < n; ++row) {
for (int col = 0; col < m; ++col) {
// Right shift by 1: bit 1 becomes bit 0
board[row][col] >>= 1;
}
}
}
};
Complexity Analysis:
- Time Complexity:
O(m * n)— each cell is visited once, and each has 8 neighbors. - Space Complexity:
O(1)extra — done in-place, no additional grid used.
🧠 Bit Trick Recap:
- We use two bits per cell:
- board[row][col] & 1 → gets the current state
- board[row][col] |= 2 → sets the next state
- board[row][col] >>= 1 → moves next state into current state position