Problem statement

The board is an m × n grid where each cell is live (1) or dead (0). Every cell interacts with its eight neighbours; all cells update simultaneously according to four rules:

1. A live cell with fewer than two live neighbours dies.
2. A live cell with two or three live neighbours lives on.
3. A live cell with more than three live neighbours dies.
4. A dead cell with exactly three live neighbours becomes live.

Return the next state of the board.

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

Example 2

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

Example 3

Input: board = [[0]]
Output: [[0]]

Constraints

• 1 <= board.length, board[i].length <= 8
• board[i][j] is 0 or 1.

Follow-up: Can you do it in place? The trap is that an updated cell must not influence its neighbours' updates.

Hints for Game of Life

1. Hint 1

   Count each cell's eight live neighbours from the original board.

2. Hint 2

   Writing into a fresh board sidesteps the simultaneity problem entirely.

3. Hint 3

   For an in-place version, encode both states in one cell — for instance, 2 for 'was dead, becomes live' — and strip the encoding in a second pass.

How to solve Game of Life

Count each cell's live neighbours from the original board and write the next state into a fresh board, so every update sees the pre-transition state.

Approach

1. For each cell, sum the eight in-bounds neighbours.
2. A live cell survives with 2 or 3 neighbours; a dead cell is born with exactly 3.
3. Return the new board.

Why it works

The rules are defined on the simultaneous previous generation; reading only the original board and writing elsewhere is the simplest way to honour that.

Complexity

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

Pitfalls

• The in-place variant encodes both generations in one cell (e.g. 2 = dead → live, 3 = live → dead) and decodes in a second pass.

Reference solution

Python

def gameOfLife(board):
    m, n = len(board), len(board[0])
    out = []
    for r in range(m):
        row = []
        for c in range(n):
            live = 0
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == 0 and dc == 0:
                        continue
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n:
                        live += board[nr][nc]
            if board[r][c] == 1:
                row.append(1 if live in (2, 3) else 0)
            else:
                row.append(1 if live == 3 else 0)
        out.append(row)
    return out

Java

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

C++

vector<vector<int>> gameOfLife(vector<vector<int>>& board) {
    int m = (int) board.size(), n = (int) board[0].size();
    vector<vector<int>> out(m, vector<int>(n, 0));
    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 += board[nr][nc];
                }
            }
            if (board[r][c] == 1) out[r][c] = (live == 2 || live == 3) ? 1 : 0;
            else out[r][c] = live == 3 ? 1 : 0;
        }
    }
    return out;
}

JavaScript

var gameOfLife = function(board) {
    const m = board.length, n = board[0].length;
    const out = [];
    for (let r = 0; r < m; r++) {
        const row = [];
        for (let c = 0; c < n; c++) {
            let live = 0;
            for (let dr = -1; dr <= 1; dr++) {
                for (let dc = -1; dc <= 1; dc++) {
                    if (dr === 0 && dc === 0) continue;
                    const nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) live += board[nr][nc];
                }
            }
            if (board[r][c] === 1) row.push(live === 2 || live === 3 ? 1 : 0);
            else row.push(live === 3 ? 1 : 0);
        }
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium