Game of Life

MediumMatrix · Simulation · In-place State Encoding🧩 Matrix Traversal LeetCode #289 ↗Updated Oct 30, 2026

Problem

An m x n grid board holds cells that are alive (1) or dead (0). Advance it by one generation, where every cell looks at its 8 neighbours at the same moment: a live cell survives only with 2 or 3 live neighbours, and a dead cell comes alive with exactly 3. Update board in-place.

Input[[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]]

Input[[1,1],[1,0]]Output[[1,1],[1,1]]

1 ≤ m, n ≤ 25 · board[i][j] is 0 or 1 · Follow-up: solve it in-place with O(1) extra memory.

Try it yourself

Java

class Solution {
    public void gameOfLife(int[][] board) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Each cell needs only 1 bit today but an int has 32. Store the next state in bit 1 while bit 0 keeps the current state, so neighbours still read the old value with & 1; finish with one >> 1 sweep.

PatternMatrix Traversal

Instinct A 2D grid you must walk in a fixed geometric order (spiral, diagonal, layer, rotate) or update in place - think boundaries, direction vectors and index maths.

Memory hack Walk the walls, then shrink the room - four fences (top, bottom, left, right) close in after every lap.

Open the Matrix Traversal guide →

Approaches

Brute ForceFull Snapshot Copy

Time O(m·n)Space O(m·n)

Copy the whole grid first. Every neighbour count reads the frozen copy, so cells that were already rewritten in board can’t corrupt later counts — that is exactly the “simultaneous update” rule.

Java

public void gameOfLife(int[][] board) {
    int m = board.length, n = board[0].length;
    int[][] old = new int[m][];
    for (int r = 0; r < m; r++) old[r] = board[r].clone();
    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 && nr < m && nc >= 0 && nc < n) live += old[nr][nc];
                }
            }
            if (old[r][c] == 1) board[r][c] = (live == 2 || live == 3) ? 1 : 0;
            else board[r][c] = (live == 3) ? 1 : 0;
        }
    }
}

Obviously correct, but doubles the memory.

BetterRolling Two-Row Buffer

Time O(m·n)Space O(n)

While writing row r, only rows r-1 and r have been touched; row r+1 is still original. So it is enough to remember the original copies of the previous row and the current row — two arrays of length n.

Java

public void gameOfLife(int[][] board) {
    int m = board.length, n = board[0].length;
    int[] prev = null;               // original row r-1
    for (int r = 0; r < m; r++) {
        int[] cur = board[r].clone(); // original row r
        int[] next = r + 1 < m ? board[r + 1] : null; // untouched yet
        for (int c = 0; c < n; c++) {
            int live = count(prev, c, n) + count(next, c, n) + count(cur, c, n) - cur[c];
            if (cur[c] == 1) board[r][c] = (live == 2 || live == 3) ? 1 : 0;
            else board[r][c] = (live == 3) ? 1 : 0;
        }
        prev = cur;
    }
}

// live cells among row[c-1..c+1]
private int count(int[] row, int c, int n) {
    if (row == null) return 0;
    int s = row[c];
    if (c > 0) s += row[c - 1];
    if (c + 1 < n) s += row[c + 1];
    return s;
}

Cuts memory to one row-width, but still not O(1).

OptimalTwo-Bit In-place Encoding

Time O(m·n)Space O(1)

Pass 1: count live neighbours using board[x][y] & 1 (the old state) and, if the cell lives next generation, set bit 1 with |= 2. Bit 0 is never changed, so later cells still see the old grid. Pass 2: board[r][c] >>= 1 promotes the new state.

Java

public 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 nr = Math.max(0, r - 1); nr <= Math.min(m - 1, r + 1); nr++) {
                for (int nc = Math.max(0, c - 1); nc <= Math.min(n - 1, c + 1); nc++) {
                    live += board[nr][nc] & 1; // bit 0 = current state
                }
            }
            live -= board[r][c] & 1;          // don't count the cell itself
            boolean alive = (board[r][c] & 1) == 1;
            if (live == 3 || (alive && live == 2)) board[r][c] |= 2; // bit 1 = next state
        }
    }
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) board[r][c] >>= 1;
    }
}

Same time, zero extra memory — answers the follow-up.

Pro tip

Name the two bits explicitly (“bit 0 = now, bit 1 = next”); the same trick extends to infinite boards by storing only live coordinates in a set.

At a glance

Level	Approach	Time	Space
Brute Force	Full Snapshot Copy	`O(m·n)`	`O(m·n)`
Better	Rolling Two-Row Buffer	`O(m·n)`	`O(n)`
Optimal	Two-Bit In-place Encoding	`O(m·n)`	`O(1)`

Common pitfalls

Updating cells in-place with plain 0/1 — later neighbours read already-updated values.
Counting the centre cell as its own neighbour.
Reading board[x][y] instead of board[x][y] & 1 once bit 1 can be set.

Interview tips

Start with the copy, then ask “what do I really need to remember?”
Condense the rules: next = (live == 3) || (alive && live == 2).
Mention the infinite-board follow-up: sparse set of live cells.

Pattern

In-place state encoding → simultaneous grid updates where old and new values must coexist in the same cell.

My notes saved in this browser