Game of Life

mediumWeak areas: redo your mistakes notebook + new421 stepsJava · Python · C++

Compute the next generation of Conway's Game of Life in place. Every cell must use the old states of its neighbours, so encode transitions in the cell itself: bit 0 is the current state, bit 1 the next state. After filling every cell's next bit, shift everything right by one.

▶ Watch the animated trace

Traced input: board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]] → [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]. Original problem: leetcode.com/problems/game-of-life/

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(1)

Each cell checks 8 neighbours.

Key idea

Rules: a live cell with 2 or 3 live neighbours lives; a dead cell with exactly 3 becomes alive; everything else dies or stays dead.
board[r][c] & 1 is still the original state while you're writing bit 1.
A final >>= 1 turns next states into current states.

Common mistakes

Updating cells directly corrupts their neighbours' counts.
Counting the cell itself as a neighbour.
Copying the board works but uses O(m·n) space.

Solution

Java

void gameOfLife(int[][] board) {
    int m = board.length, n = board[0].length;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int live = 0;
            for (int dr = -1; dr <= 1; dr++)
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    int nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nc >= 0 && nr < m && nc < n) live += board[nr][nc] & 1;
                }
            boolean alive = (board[r][c] & 1) == 1;
            if ((alive && (live == 2 || live == 3)) || (!alive && live == 3)) board[r][c] |= 2;
        }
    }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) board[r][c] >>= 1;
}

Python

def gameOfLife(board: List[List[int]]) -> None:
    m, n = len(board), len(board[0])
    for r in range(m):
        for c in range(n):
            live = sum(board[nr][nc] & 1
                       for nr in range(r - 1, r + 2) for nc in range(c - 1, c + 2)
                       if (nr, nc) != (r, c) and 0 <= nr < m and 0 <= nc < n)
            alive = board[r][c] & 1
            if (alive and live in (2, 3)) or (not alive and live == 3): board[r][c] |= 2
    for r in range(m):
        for c in range(n): board[r][c] >>= 1

C++

void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int live = 0;
            for (int dr = -1; dr <= 1; dr++)
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    int nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nc >= 0 && nr < m && nc < n) live += board[nr][nc] & 1;
                }
            bool alive = board[r][c] & 1;
            if ((alive && (live == 2 || live == 3)) || (!alive && live == 3)) board[r][c] |= 2;
        }
    }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) board[r][c] >>= 1;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Block stays still Each cell has 3 live neighbours.	`board = [[1, 1], [1, 1]]`	`[[1, 1], [1, 1]]`
Lonely cell dies Zero neighbours: underpopulation.	`board = [[1]]`	`[[0]]`
Blinker flips The vertical line becomes horizontal.	`board = [[0, 1, 0], [0, 1, 0], [0, 1, 0]]`	`[[0, 0, 0], [1, 1, 1], [0, 0, 0]]`