Game of Life

Medium Arrays & Hashing In-place Transformations Original on LeetCode

Reported atAdobe

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].length
  • 1 <= m, n <= 25
  • board[i][j] is 0 or 1

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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(m · n)Each cell looks at 8 neighbours, a constant.
SpaceO(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.

  1. Copy every row of the board.
  2. For every cell, count live neighbours among the 8 surrounding cells of the copy (skipping cells outside the grid).
  3. 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;
            }
        }
    }
}

2Optimal (two states in one cell)

TimeO(m · n)Two passes over the grid, each with constant work per cell.
SpaceO(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.

  1. For every cell, count live neighbours using board[r][c] & 1.
  2. If the cell should be alive in the next step, set bit 1: board[i][j] |= 2.
  3. 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;
        }
    }
}

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.