Game of Life
Description
The board is an m × n grid of cells, each live (1) or dead (0). A cell's neighbours are the up to eight cells touching it, across, up and down, or diagonally. One step of Conway's Game of Life gives every cell its next state:
- A live cell with 2 or 3 live neighbours stays alive; with fewer or more, it dies.
- A dead cell with exactly 3 live neighbours comes alive; otherwise it stays dead.
Every cell changes at the same moment, so each next state is worked out from the board as it was before the step. Change board in place to its next state; the function returns nothing.
Follow-up: can you do it without a copy of the board, in O(1) extra space?
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]]
Explanation: Every count is taken on the board as it was. (0, 1) and (2, 0) have 1 live neighbour each, so they die; (1, 2), (2, 1) and (2, 2) have 3, 3 and 2 live neighbours, so they live on; (1, 0) and (3, 1) are dead with exactly 3, so they come alive.
Example 2
Input: board = [[1, 1], [1, 0]]
Output: [[1, 1], [1, 1]]
Explanation: (0, 0), (0, 1) and (1, 0) have 2 live neighbours each, so they live on; (1, 1) is dead with exactly 3, so it comes alive.
Example 3
Input: board = [[1]]
Output: [[0]]
Explanation: (0, 0) has no live neighbours, so it dies.
Constraints
- m == board.length
- n == board[i].length
- 1 ≤ m, n ≤ 25
- board[i][j] is 0 or 1
Editorial
Brute Force
Intuition
Every cell's next state depends on its neighbours as they are now, but the answer goes into the same board. So copy the board first, count each cell's live neighbours on the copy, and write the new state into the board. The cells already written never feed into a count.
Step-by-Step Explanation
Let's trace Example 1, board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]:
- Copy the board; every count below reads the copy, the board as it was.
- Row 0: (0, 0) has 1 live neighbour and stays dead; (0, 1) has 1 and dies; (0, 2) has 2 and stays dead.
- Row 1: (1, 0) has 3 live neighbours and comes alive; (1, 1) has 5 and stays dead; (1, 2) has 3 and lives on.
- Row 2: (2, 0) has 1 live neighbour and dies; (2, 1) has 3 and lives on; (2, 2) has 2 and lives on.
- Row 3: (3, 0) has 2 live neighbours and stays dead; (3, 1) has 3 and comes alive; (3, 2) has 2 and stays dead.
- The board now holds [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]].
Count on a Copy — Each cell's live neighbours on the copy, one cell at a time, then the new board.
Algorithm
- Copy the board.
- For each cell, count the live cells among the up to eight around it, on the copy.
- Write 1 if the count is 3, or if the cell was alive and the count is 2; otherwise write 0.
Code
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int rows = board.size(), cols = board[0].size();
vector<vector<int>> old = board; // the board as it was
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += old[nr][nc];
}
board[r][c] = (live == 3 || (old[r][c] == 1 && live == 2)) ? 1 : 0;
}
}
};
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
rows, cols = len(board), len(board[0])
old = [row[:] for row in board] # the board as it was
for r in range(rows):
for c in range(cols):
live = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if (dr or dc) and 0 <= nr < rows and 0 <= nc < cols:
live += old[nr][nc]
board[r][c] = 1 if live == 3 or (old[r][c] == 1 and live == 2) else 0
class Solution {
public void gameOfLife(int[][] board) {
int rows = board.length, cols = board[0].length;
int[][] old = new int[rows][];
for (int r = 0; r < rows; r++) old[r] = board[r].clone(); // the board as it was
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += old[nr][nc];
}
board[r][c] = (live == 3 || (old[r][c] == 1 && live == 2)) ? 1 : 0;
}
}
}
var gameOfLife = function(board) {
const rows = board.length, cols = board[0].length;
const old = board.map(row => row.slice()); // the board as it was
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) {
let live = 0;
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if ((dr || dc) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += old[nr][nc];
}
board[r][c] = (live === 3 || (old[r][c] === 1 && live === 2)) ? 1 : 0;
}
};
Complexity Analysis
Time Complexity: O(m × n)
Each cell looks at its at most 8 neighbours.
Space Complexity: O(m × n)
The copy of the board.
Why This Approach Is Not Efficient
The copy takes m × n more cells to keep one bit of each: whether it was alive. A cell holds 0 or 1, so its state now fits in bit 0 and its next state in bit 1 of the same number. Counting a neighbour then reads bit 0 alone, board[nr][nc] & 1, whatever bit 1 already says.
Optimal Approach - Two States in One Cell
Intuition
Keep both generations in the board. Bit 0 of each cell is its state now, bit 1 its state next. The first pass counts live neighbours by bit 0 alone, so a cell that's already marked still counts as it was, and sets bit 1 when the cell is alive next: 2 means dead now and alive next, 3 alive now and next. The second pass shifts every cell right by one bit, which drops the old state and keeps the new one.
Step-by-Step Explanation
Let's trace Example 1 again, board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]:
- Row 0: (0, 1) has 1 live neighbour, so bit 1 stays 0 and it stays 1; the row stays 0 1 0.
- Row 1: (1, 0) has 3 live neighbours, so it becomes 2; (1, 2) has 3 live neighbours, so it becomes 3. 0 0 1 is now 2 0 3.
- Row 2: (2, 0) has 1 live neighbour, so bit 1 stays 0 and it stays 1; (2, 1) has 3 live neighbours, 1 of them already marked 3, so it becomes 3; (2, 2) has 2 live neighbours, 2 of them already marked 3, so it becomes 3. 1 1 1 is now 1 3 3.
- Row 3: (3, 1) has 3 live neighbours, 2 of them already marked 3, so it becomes 2. 0 0 0 is now 0 2 0.
- Shift every cell right by one bit: the board becomes [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]].
Two States in One Cell — Bit 1 set in each cell that's alive next, counting neighbours by bit 0, then the shift.
Algorithm
- For each cell, count the live cells among the up to eight around it, reading only bit 0:
board[nr][nc] & 1. - If the count is 3, or the cell is alive (bit 0 is 1) and the count is 2, set bit 1:
board[r][c] |= 2. - Shift every cell right by one bit:
board[r][c] >>= 1.
Code
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int rows = board.size(), cols = board[0].size();
for (int r = 0; r < rows; r++) // bit 0: alive now; bit 1: alive next
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live == 3 || ((board[r][c] & 1) && live == 2)) board[r][c] |= 2; // alive next
}
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) board[r][c] >>= 1; // next becomes now
}
};
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
rows, cols = len(board), len(board[0])
for r in range(rows): # bit 0: alive now; bit 1: alive next
for c in range(cols):
live = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if (dr or dc) and 0 <= nr < rows and 0 <= nc < cols:
live += board[nr][nc] & 1 # the neighbour as it is now
if live == 3 or (board[r][c] & 1 and live == 2):
board[r][c] |= 2 # alive next
for r in range(rows):
for c in range(cols):
board[r][c] >>= 1 # next becomes now
class Solution {
public void gameOfLife(int[][] board) {
int rows = board.length, cols = board[0].length;
for (int r = 0; r < rows; r++) // bit 0: alive now; bit 1: alive next
for (int c = 0; c < cols; c++) {
int live = 0;
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr, nc = c + dc;
if ((dr != 0 || dc != 0) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live == 3 || ((board[r][c] & 1) == 1 && live == 2)) board[r][c] |= 2; // alive next
}
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) board[r][c] >>= 1; // next becomes now
}
}
var gameOfLife = function(board) {
const rows = board.length, cols = board[0].length;
for (let r = 0; r < rows; r++) // bit 0: alive now; bit 1: alive next
for (let c = 0; c < cols; c++) {
let live = 0;
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if ((dr || dc) && nr >= 0 && nr < rows && nc >= 0 && nc < cols)
live += board[nr][nc] & 1; // the neighbour as it is now
}
if (live === 3 || ((board[r][c] & 1) && live === 2)) board[r][c] |= 2; // alive next
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) board[r][c] >>= 1; // next becomes now
};
Complexity Analysis
Time Complexity: O(m × n)
Two passes over the cells; the first looks at at most 8 neighbours each.
Space Complexity: O(1)
The next state lives in bit 1 of each cell; besides that, a few counters.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Updating the board as you go. board[r][c] = 1 if live == 3 or (board[r][c] and live == 2) else 0
On board = [[1, 1, 1]] it leaves board as [[0, 0, 0]]; the answer is [[0, 1, 0]]. Every cell's next state depends on its neighbours as they are now. Writing each new state straight into the board means the cells after it count neighbours that have already moved on a generation.
Counting a marked cell as dead. live += board[nr][nc] == 1
On board = [[1, 1], [1, 1]] it leaves board as [[1, 1], [0, 0]]; the answer is [[1, 1], [1, 1]]. Once a cell is marked, it holds 2 or 3, not 0 or 1. Only bit 0 says whether it is alive now, so the count has to read board[nr][nc] & 1; testing for 1 misses every neighbour already marked to live on.
Checking only the far edges. if (dr or dc) and nr < rows and nc < cols:
On board = [[0, 0, 0], [0, 0, 0], [1, 1, 1]] it leaves board as [[1, 1, 0], [1, 1, 0], [1, 1, 0]]; the answer is [[0, 0, 0], [0, 1, 0], [0, 1, 0]]. In Python, board[-1] is the last row and row[-1] the last column, so nothing fails when r − 1 or c − 1 is −1: cells on the top row and left column quietly count neighbours from the far side of the board.
Where This Pattern Is Taught
This problem practises changing a matrix in place while every cell still needs the old values around it, by keeping the new state beside the old one in a second bit. It's taught in Changing a Matrix in Place.