Game of Life
Game of Life is a medium arrays & hashing problem solved with the in-place transformations pattern.
The best approach, optimal (two states in one cell), runs in O(m · n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy the board) up.
Problem
A board of m x n cells is given, where 1 means a cell is alive and 0 means it is dead. Each cell has up to eight neighbours (horizontal, vertical and diagonal). One step of the simulation updates every cell at the same time using these rules:
- A live cell with fewer than two live neighbours dies (loneliness).
- A live cell with two or three live neighbours stays alive.
- A live cell with more than three live neighbours dies (overcrowding).
- A dead cell with exactly three live neighbours becomes alive.
Update board in place to the state after one step. Nothing is returned.
Examples
Example 1
- Input
board = [[1, 1, 0], [1, 0, 0], [0, 0, 1]]- Output
[[1, 1, 0], [1, 0, 0], [0, 0, 0]]- Why
- The three live cells in the top-left corner each have two live neighbours and survive. The dead cell at (1, 1) touches four live cells, so it stays dead. The lonely cell at (2, 2) dies.
Example 2
- Input
board = [[0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]]- Output
[[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 1, 0]]- Why
- A horizontal bar of three flips to a vertical bar: the middle cell survives, the two ends die, and the cells above and below the middle are born.
Example 3
- Input
board = [[1]]- Output
[[0]]- Why
- A single live cell has no neighbours, so it dies.
Constraints
m == board.length,n == board[i].length1 <= m, n <= 25board[i][j]is0or1
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (copy the board) | O(m · n) | O(m · n) |
| Optimal (two states in one cell) | O(m · n) | O(1) |
1Brute force (copy the board)
O(m · n)Each cell looks at 8 neighbours, a constant.O(m · n)The full copy of the board.Make a copy of the board. Count each cell's live neighbours in the copy, and write the new state into the original board, so updates never affect the counting.
- Copy every row of the board.
- For every cell, count live neighbours among the 8 surrounding cells of the copy (skipping cells outside the grid).
- Live with 2 or 3 neighbours stays alive; dead with exactly 3 becomes alive; everything else becomes dead.
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length, n = board[0].length;
int[][] old = new int[m][];
for (int i = 0; i < m; i++) old[i] = board[i].clone();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int live = 0;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) continue;
int r = i + di, c = j + dj;
if (r >= 0 && r < m && c >= 0 && c < n) live += old[r][c];
}
}
if (old[i][j] == 1) board[i][j] = (live == 2 || live == 3) ? 1 : 0;
else board[i][j] = live == 3 ? 1 : 0;
}
}
}
}class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
m, n = len(board), len(board[0])
old = [row[:] for row in board]
for i in range(m):
for j in range(n):
live = 0
for di in (-1, 0, 1):
for dj in (-1, 0, 1):
if di == 0 and dj == 0:
continue
r, c = i + di, j + dj
if 0 <= r < m and 0 <= c < n:
live += old[r][c]
if old[i][j] == 1:
board[i][j] = 1 if live in (2, 3) else 0
else:
board[i][j] = 1 if live == 3 else 0class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = board[0].size();
vector<vector<int>> old = board;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int live = 0;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) continue;
int r = i + di, c = j + dj;
if (r >= 0 && r < m && c >= 0 && c < n) live += old[r][c];
}
}
if (old[i][j] == 1) board[i][j] = (live == 2 || live == 3) ? 1 : 0;
else board[i][j] = live == 3 ? 1 : 0;
}
}
}
};function gameOfLife(board) {
const m = board.length, n = board[0].length;
const old = board.map(row => row.slice());
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let live = 0;
for (let di = -1; di <= 1; di++) {
for (let dj = -1; dj <= 1; dj++) {
if (di === 0 && dj === 0) continue;
const r = i + di, c = j + dj;
if (r >= 0 && r < m && c >= 0 && c < n) live += old[r][c];
}
}
if (old[i][j] === 1) board[i][j] = (live === 2 || live === 3) ? 1 : 0;
else board[i][j] = live === 3 ? 1 : 0;
}
}
}2Optimal (two states in one cell)
O(m · n)Two passes over the grid, each with constant work per cell.O(1)The next state lives in the unused bit of each cell; no extra grid.Each cell only uses bit 0. Use bit 1 to hold the next state. While counting, read only bit 0 (cell & 1), so cells already updated still report their old value. A final pass shifts every cell right by one to make the next state current.
- For every cell, count live neighbours using
board[r][c] & 1. - If the cell should be alive in the next step, set bit 1:
board[i][j] |= 2. - After all cells are processed, replace every cell with
board[i][j] >> 1.
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int live = 0;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) continue;
int r = i + di, c = j + dj;
if (r >= 0 && r < m && c >= 0 && c < n) live += board[r][c] & 1;
}
}
boolean alive = (board[i][j] & 1) == 1;
if ((alive && (live == 2 || live == 3)) || (!alive && live == 3)) {
board[i][j] |= 2;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) board[i][j] >>= 1;
}
}
}class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
live = 0
for di in (-1, 0, 1):
for dj in (-1, 0, 1):
if di == 0 and dj == 0:
continue
r, c = i + di, j + dj
if 0 <= r < m and 0 <= c < n:
live += board[r][c] & 1
alive = board[i][j] & 1 == 1
if (alive and live in (2, 3)) or (not alive and live == 3):
board[i][j] |= 2
for i in range(m):
for j in range(n):
board[i][j] >>= 1class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int live = 0;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) continue;
int r = i + di, c = j + dj;
if (r >= 0 && r < m && c >= 0 && c < n) live += board[r][c] & 1;
}
}
bool alive = (board[i][j] & 1) == 1;
if ((alive && (live == 2 || live == 3)) || (!alive && live == 3)) {
board[i][j] |= 2;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) board[i][j] >>= 1;
}
}
};function gameOfLife(board) {
const m = board.length, n = board[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let live = 0;
for (let di = -1; di <= 1; di++) {
for (let dj = -1; dj <= 1; dj++) {
if (di === 0 && dj === 0) continue;
const r = i + di, c = j + dj;
if (r >= 0 && r < m && c >= 0 && c < n) live += board[r][c] & 1;
}
}
const alive = (board[i][j] & 1) === 1;
if ((alive && (live === 2 || live === 3)) || (!alive && live === 3)) {
board[i][j] |= 2;
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) board[i][j] >>= 1;
}
}Edge cases to test
- A 1 x 1 board
- A single row or a single column (cells have at most two neighbours)
- A board where every cell is alive: interior cells die of overcrowding, corners survive
- Stable shapes like a 2 x 2 block, which must stay exactly the same
Hints
Hint 1
All cells change at the same moment, so you must count neighbours using the OLD values. The easy fix is a copy of the board.
Hint 2
To avoid the copy, store the new state in a spare bit of the same int: bit 0 is the current state, bit 1 the next state.
Hint 3
Count neighbours with cell & 1, then in a second pass shift every cell right by one.
FAQ
What is the best time complexity for Game of Life?
Optimal (two states in one cell) runs in O(m · n) time and O(1) extra space. Two passes over the grid, each with constant work per cell.
Which pattern does Game of Life use?
It is a arrays & hashing problem that uses the in-place transformations pattern. Other problems with the same pattern: Set Matrix Zeroes, Find All Duplicates in an Array, First Missing Positive.
Is there a brute force solution for Game of Life?
Yes. Brute force (copy the board) takes O(m · n) time and O(m · n) space. Make a copy of the board.
Which edge cases should I test for Game of Life?
A 1 x 1 board; A single row or a single column (cells have at most two neighbours); A board where every cell is alive: interior cells die of overcrowding, corners survive; Stable shapes like a 2 x 2 block, which must stay exactly the same.