Game of Life

Problem#

Apply one step of Conway’s Game of Life to the input grid in place. Rules: a live cell with 2 or 3 live neighbors stays live; a dead cell with exactly 3 live neighbors becomes live; otherwise dies/stays dead.

Examples#

[[0,1,0],[0,0,1],[1,1,1],[0,0,0]] → [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
[[1,1],[1,0]] → [[1,1],[1,1]]

Constraints#

m == board.length, n == board[i].length, 1 <= m, n <= 25.

Approach#

Encode the next state in bit 1 while reading the current state from bit 0. After the sweep, shift everything right by one bit. Each cell counts live neighbors using board[ni][nj] & 1.

Solution#

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        int dx[8] = {1,1,1,0,0,-1,-1,-1}, dy[8] = {1,0,-1,1,-1,1,0,-1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int live = 0;
                for (int k = 0; k < 8; ++k) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
                    live += board[ni][nj] & 1;
                }
                int cur = board[i][j] & 1;
                int next = (cur && (live == 2 || live == 3)) || (!cur && live == 3);
                board[i][j] |= (next << 1);
            }
        }
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                board[i][j] >>= 1;
    }
};

func gameOfLife(board [][]int) {
    m, n := len(board), len(board[0])
    dx := [8]int{1, 1, 1, 0, 0, -1, -1, -1}
    dy := [8]int{1, 0, -1, 1, -1, 1, 0, -1}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            live := 0
            for k := 0; k < 8; k++ {
                ni, nj := i+dx[k], j+dy[k]
                if ni < 0 || ni >= m || nj < 0 || nj >= n {
                    continue
                }
                live += board[ni][nj] & 1
            }
            cur := board[i][j] & 1
            next := 0
            if (cur == 1 && (live == 2 || live == 3)) || (cur == 0 && live == 3) {
                next = 1
            }
            board[i][j] |= next << 1
        }
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            board[i][j] >>= 1
        }
    }
}

from typing import List

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        m, n = len(board), len(board[0])
        dx = [1, 1, 1, 0, 0, -1, -1, -1]
        dy = [1, 0, -1, 1, -1, 1, 0, -1]
        for i in range(m):
            for j in range(n):
                live = 0
                for k in range(8):
                    ni, nj = i + dx[k], j + dy[k]
                    if 0 <= ni < m and 0 <= nj < n:
                        live += board[ni][nj] & 1
                cur = board[i][j] & 1
                nxt = 1 if (cur == 1 and (live == 2 or live == 3)) or (cur == 0 and live == 3) else 0
                board[i][j] |= nxt << 1
        for i in range(m):
            for j in range(n):
                board[i][j] >>= 1

function gameOfLife(board) {
    const m = board.length, n = board[0].length;
    const dx = [1, 1, 1, 0, 0, -1, -1, -1];
    const dy = [1, 0, -1, 1, -1, 1, 0, -1];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let live = 0;
            for (let k = 0; k < 8; k++) {
                const ni = i + dx[k], nj = j + dy[k];
                if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
                live += board[ni][nj] & 1;
            }
            const cur = board[i][j] & 1;
            const next = (cur === 1 && (live === 2 || live === 3)) || (cur === 0 && live === 3) ? 1 : 0;
            board[i][j] |= next << 1;
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
}

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};
        int[] dy = {1, 0, -1, 1, -1, 1, 0, -1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int k = 0; k < 8; k++) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
                    live += board[ni][nj] & 1;
                }
                int cur = board[i][j] & 1;
                int next = ((cur == 1 && (live == 2 || live == 3)) || (cur == 0 && live == 3)) ? 1 : 0;
                board[i][j] |= next << 1;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }
}

function gameOfLife(board: number[][]): void {
    const m = board.length, n = board[0].length;
    const dx = [1, 1, 1, 0, 0, -1, -1, -1];
    const dy = [1, 0, -1, 1, -1, 1, 0, -1];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let live = 0;
            for (let k = 0; k < 8; k++) {
                const ni = i + dx[k], nj = j + dy[k];
                if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
                live += board[ni][nj] & 1;
            }
            const cur = board[i][j] & 1;
            const next = (cur === 1 && (live === 2 || live === 3)) || (cur === 0 && live === 3) ? 1 : 0;
            board[i][j] |= next << 1;
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
}

Editorial#

The two-bit encoding next_state << 1 | current_state keeps both states simultaneously. Subsequent cells still read the original state via & 1, so the update order doesn’t corrupt counting. A final shift extracts the next generation.

Complexity#

Time: O(m*n).
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#