Game of Life

Medium

Problem

Each cell is live (1) or dead (0). All cells update at the same time: a live cell with 2 or 3 live neighbours (out of 8) survives, otherwise it dies; a dead cell with exactly 3 live neighbours becomes live. Compute the next state in place.

Example 1

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

Test cases

Case 1

Input:    [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Expected: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Case 2

Input:    [[1,1],[1,0]]
Expected: [[1,1],[1,1]]

Case 3

Input:    [[1]]
Expected: [[0]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. In place with bit encoding

Time O(R·C)Space O(1)

Bit 0 holds the current state, bit 1 the next. Count live neighbours using (v & 1), write the next state into bit 1, then shift every cell right.

function gameOfLife(b) {
const R = b.length, C = b[0].length;
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
let live = 0;
for (let dr = -1; dr <= 1; dr++)
for (let dc = -1; dc <= 1; dc++) {
if (!dr && !dc) continue;
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < R && nc < C) live += b[nr][nc] & 1;
}
if (live === 3 || (live === 2 && (b[r][c] & 1))) b[r][c] |= 2;
}
}
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) b[r][c] >>= 1;
}