Game of Life

Medium#289old and new in one cell

You get a board of cells, 1 alive and 0 dead. Work out the next generation, all cells at once, in place. Each cell looks at its up to eight neighbours: an alive cell with 2 or 3 alive neighbours lives on, with fewer or more it dies; a dead cell with exactly 3 comes alive. Our example: [0, 0, 0], [1, 1, 1], [0, 0, 0] → [0, 1, 0], [0, 1, 0], [0, 1, 0].

289 Game of LifeWalkthrough · 1×

Example: a row of three across the middle of [0, 0, 0], [1, 1, 1], [0, 0, 0]. Watch cell (2, 1): its neighbours (1, 0) and (1, 2) are already marked to die, and they still count.

012012000111000
0: dead1: alive2: alive now, dies next3: dead now, born next

First pass: decide every cell’s next state from its neighbours as they are in this generation, without losing what it is now

01/29
restart · back · play · step
Speed
1function gameOfLife(m):
2 for each cell (r, c):
3 live = neighbours of (r, c) that are 1 or 2
4 if m[r][c] == 1 and (live < 2 or live > 3):
5 m[r][c] = 2 // alive now, dead next
6 else if m[r][c] == 0 and live == 3:
7 m[r][c] = 3 // dead now, alive next
8 for each cell (r, c):
9 m[r][c] = m[r][c] mod 2 // keep the new state
10 return m
state
r
–
c
–
live
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every cell must be decided from the board as it was. Writing 0 or 1 at once would change the count of the cells after it: (2, 1) would see one alive neighbour instead of three and stay dead.
  2. The marks keep both states in one cell: 1 or 2 means alive now, 0 or 3 dead now, so a count stays right while the board fills with decisions; 2 or 3 also says the cell changes.
  3. Once every cell is decided, the old states are no longer needed. The new state is the value mod 2 (0 and 2 are dead next, 1 and 3 alive), so the second pass is one line with no checks.

Complexity

Time O(rows × columns): each cell looks at its at most eight neighbours once, then is decoded once. Memory O(1): no copy of the board, the marks live in the cells.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.