Game of Life

Table of Contents +

Game of Life sounds fun, but it hides a real trap. Every cell updates based on its neighbors. So if you change a cell too early, the next cell reads a wrong, already-changed neighbor. The interviewer wants to see if you can update the whole board at once, in place, without that mistake. The clever fix is to encode both the old and new state in one number.

🎯 The Problem

You get a board, which is a grid of cells. Each cell is alive, shown as 1, or dead, shown as 0. The board moves to the next step using simple rules.

A neighbor is any of the eight cells touching a cell, including the diagonal ones.

The rules:

A live cell with fewer than two live neighbors dies.
A live cell with two or three live neighbors lives.
A live cell with more than three live neighbors dies.
A dead cell with exactly three live neighbors becomes alive.
All cells update at the same moment based on the current board.
You must change the 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

Explanation: every cell updates at once using its eight neighbors.

Here is one cell and the eight neighbors that decide its fate.

🐢 Approach 1: Copy the Board First (Brute Force)

The idea:

Make a full copy of the board.
Read neighbors from the copy, which never changes.
Write results into the real board.

How it works:

The copy stays frozen, so every cell sees the correct original neighbors.
It is correct and easy to explain.

Why it is weak:

It uses a second board the same size as the input.
So the extra space is O(m × n).
The interviewer almost always asks for an in-place version.

Here is the copy-board code:

def game_of_life(board):
    rows, cols = len(board), len(board[0])
    old = [row[:] for row in board]

    for r in range(rows):
        for c in range(cols):
            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 < rows and 0 <= nc < cols:
                        live += old[nr][nc]
            board[r][c] = 1 if live == 3 or (old[r][c] == 1 and live == 2) else 0

⚡ Approach 2: Encode Both States In One Number (Best)

The idea in one line: hide the old state inside each cell with extra codes, so you can update in place and still read correct old neighbors.

The codes:

Keep 0 and 1 meaning the same as before.
Code 2 means “was alive, now dead.”
Code 3 means “was dead, now alive.”

The trick that makes it work:

The old state is whether the number is odd. 1 and 3 are odd, so they were alive. 0 and 2 are even, so they were dead.
When counting neighbors, ask “was this neighbor alive before?” That is true when the cell is 1 or 2, both odd-state alive cells before the change.
The old value is never lost, because it lives in the code.

How it finishes:

After the whole board is encoded, do a clean pass.
Replace 2 with 0 and 3 with 1. Map 1 and 0 to themselves.
Taking the value modulo 2 does all of this at once.

Why it is fast:

It reuses the board, so the extra space is just O(1).
Each cell still checks eight neighbors, which is constant work.

Steps to Solve

For each cell, count its live neighbors by checking which of the eight are 1 or 3.
If the cell is alive and has two or three live neighbors, it stays alive, so leave it.
If the cell is alive and the rule says it dies, write 2.
If the cell is dead and has exactly three live neighbors, write 3.
After visiting every cell, do a clean pass. Turn 2 into 0 and 3 into 1.

Here is the encode-then-clean flow.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version counts neighbors with the old state, encodes 2 and 3, then cleans with modulo.

def game_of_life(board):
    rows = len(board)
    cols = len(board[0])
    for i in range(rows):
        for j in range(cols):
            live = 0
            for di in (-1, 0, 1):                 # look at 8 neighbors
                for dj in (-1, 0, 1):
                    if di == 0 and dj == 0:
                        continue
                    ni, nj = i + di, j + dj
                    if 0 <= ni < rows and 0 <= nj < cols:
                        if board[ni][nj] in (1, 2):  # was alive before
                            live += 1
            if board[i][j] == 1 and (live < 2 or live > 3):
                board[i][j] = 2                   # was alive, now dead
            if board[i][j] == 0 and live == 3:
                board[i][j] = 3                   # was dead, now alive
    for i in range(rows):
        for j in range(cols):
            board[i][j] %= 2                      # 2->0, 3->1


board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]
game_of_life(board)
for row in board:
    print(" ".join(str(v) for v in row))

The output of the above code will be:

Let us read the Python version line by line, because the encoding is the part that makes it work.

The two outer loops over i and j visit every cell. For each cell we set live = 0 and then count its live neighbors.

The two inner loops over di and dj step through the offsets -1, 0, and 1. Together they reach all nine cells around and including the current one. The line if di == 0 and dj == 0: continue skips the cell itself, so we look only at the eight neighbors.

ni, nj = i + di, j + dj is the neighbor position. The check if 0 <= ni < rows and 0 <= nj < cols keeps us inside the board, so we never read off the edge.

Now the key line. if board[ni][nj] in (1, 2) asks “was this neighbor alive before this step?” We count 1 and 2 as alive. Here is why. A cell still showing 1 was alive and we have not changed it. A cell showing 2 was also alive before, but we marked it to die this step. Both had an old state of alive. So both count. We do not count 3, because 3 means “was dead, now alive.” Its old state was dead. This is the whole point of the encoding. The new codes still let us read the old state of any neighbor.

After counting, the two if blocks apply the rules. A live 1 cell that breaks the survival rule becomes 2. A dead 0 cell with exactly three live neighbors becomes 3. We never destroy the old value, because the new codes still tell us the old state.

The final double loop runs board[i][j] %= 2. That turns 2 into 0 and 3 into 1, and leaves 0 and 1 alone. After this pass the board holds only 0 and 1 again, now in the next-step shape.

⏱️ Time and Space Complexity

For each cell we look at eight neighbors, which is a constant amount of work. So the time is O(m × n). The copy approach needs a second board, so its space is O(m × n). The encoded approach reuses the board, so its extra space is O(1).

Approach	Time Complexity	Space Complexity
Copy the board	O(m × n)	O(m × n)
Encoded states in place	O(m × n)	O(1)

Tip

The whole board updates at the same moment. So you must never let a changed cell look like a changed neighbor. Encoding the old state into the same number is what protects you from that mistake.

🧩 Key Takeaways

✅ Every cell updates at once, so changing a cell early would corrupt its neighbors.
✅ Encode the next state into new codes so the old state is never lost.
✅ Use a clean second pass to map the codes back to plain 0 and 1.
✅ Each cell checks eight neighbors, which is constant work per cell.
✅ The encoded approach updates in place, so the extra space is O(1).

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Set Matrix Zeroes
Spiral Matrix

Previous Diagonal Traverse Next Happy Number

Game of Life

Follow Us

Follow Us