Game of Life Interview Question: Solve It in Place

In this article

1. Before you start
2. Why interviewers ask this
3. Game of Life from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview questions learning path, and the code is Python.

Why interviewers ask this

A wrong answer to this problem passes the first small example and fails on the next, because the bug only appears when a cell is read after it was already overwritten. That makes it a quick test of whether a candidate thinks about the order of reads and writes.

On LeetCode the problem is number 289 and is rated Medium. It is reported by candidates in coding rounds; no public source ties it to a named company.

A weak answer builds a second board and never mentions memory. A strong answer states the simultaneous-update rule first, then writes a copy-free version. A Staff-level answer adds what breaks next: the follow-up on an infinite board, where an array stops being a good model.

Game of Life from first principles

Game of Life

The Game of Life is a zero-player game on a grid of cells, each live or dead, in which a fixed rule on the eight surrounding cells decides every cell's next state, so the starting pattern alone fixes everything that follows.

Sentinel value

A sentinel value is a special value outside the normal range of the data that a program uses to signal a condition, such as the end of a list or, in this problem, a cell whose state will change, while the value still lets the old state be read.

In-place algorithm

An in-place algorithm is a procedure that transforms its input inside the memory it was given, using only a constant amount of extra memory instead of a second copy of the data.

In plain words

Picture a street of houses, each with a porch light. Every night, at the same time, each household looks at the eight houses around it, including the diagonal ones, and decides whether its own light stays on. The analogy breaks in one place. Real households could glance at a neighbour who has already switched, but on the board every cell must judge a frozen snapshot of the night before.

A cellular automaton is a grid of cells, each in one of a few states, that all update together by one fixed local rule. The Game of Life is the best-known one. Wikipedia says the British mathematician John Horton Conway devised it in 1970 and that its evolution is determined by its initial state, with no further input. A generation is one complete update of every cell on the board.

In one precise sentence: the next board is a function of the current board only, applied to all cells together.

Step 1: Count the eight live neighbours of a cell

Counting the live neighbours of every cell from the old board is step one. The neighbours of a cell are the eight cells directly next to it horizontally, vertically or diagonally, as LifeWiki states. The cell itself is never counted.

The input is a board and a position. The output is a number from zero to eight. On a finite array, a corner cell has only three neighbours inside the grid and an edge cell has five, and the code treats everything outside the array as dead.¹

DIRECTIONS = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
              (0, 1), (1, -1), (1, 0), (1, 1)]

def live_neighbours(board, i, j):
    m, n = len(board), len(board[0])
    count = 0
    for di, dj in DIRECTIONS:
        r, c = i + di, j + dj
        if 0 <= r < m and 0 <= c < n and board[r][c] > 0:
            count += 1
    return count

The test board[r][c] > 0 looks odd for a board of zeros and ones. It is deliberate, and Step 3 explains why. You now have the one helper the rest of the solution relies on.

Step 2: Apply the four rules to every cell at once

Each cell's next state follows four rules, as the problem statement lists them. A live cell with fewer than two live neighbours dies (under-population). A live cell with two or three live neighbours survives. A live cell with more than three live neighbours dies (over-population). A dead cell with exactly three live neighbours becomes live (reproduction). The compact name for these rules is B3/S23: born with three, survive with two or three (LifeWiki).

The rules fold into one test. A cell is live next generation if its count is three, or if the cell is live now and its count is two.

The word that matters is "simultaneously". The statement requires the rules to be applied to every cell of the current state together, and one mirror of the problem spells out that you cannot update some cells first and then use their updated values for others. Both Wikipedia and LifeWiki say each generation is a pure function of the one before. The input of this step is the old board; its output is a decision per cell, not yet written anywhere.

Step 3: Mark changes with sentinel values so old states survive

Step three marks changes with sentinel values so old states survive. If you write a new 0 or 1 into a cell the moment you decide it, the next cell on the row reads that new value as if it were old, and its count is wrong. The board is corrupted without any error message.

The fix, reported in a mirror of the problem, gives each changing cell a marker. State 2 means a live cell becomes dead, and state -1 means a dead cell becomes live. Cells that keep their state stay 0 or 1.¹

Now neighbour counting needs one rule: a cell was live in the old board if its value is above zero. A 1 was live and stays live, a 2 was live and is dying, a 0 was dead and stays dead, and a -1 was dead and is being born. That is why Step 1 tests > 0 instead of == 1.

def mark_changes(board):
    for i in range(len(board)):
        for j in range(len(board[0])):
            n = live_neighbours(board, i, j)
            if board[i][j] > 0 and (n < 2 or n > 3):
                board[i][j] = 2    # was live, will die
            elif board[i][j] == 0 and n == 3:
                board[i][j] = -1   # was dead, will be born

Step 4: Run a second pass to turn markers into final values

A second pass replaces each marker with its final value: 2 becomes 0 and -1 becomes 1.¹ No neighbour counting happens in this pass, so the order of the scan no longer matters.

def game_of_life(board):
    mark_changes(board)
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == 2:
                board[i][j] = 0
            elif board[i][j] == -1:
                board[i][j] = 1

The cost follows from the loops. Each of the m × n cells checks eight neighbours, so time is O(m×n) per generation, and the extra memory is a few variables, so it is O(1). The simplest alternative, copying the whole board first, costs memory proportional to the board. The whole procedure is two passes over the grid.

1 · Count2 · Decide3 · Mark4 · FinaliseReplay

Step-by-step description

1. Count the eight neighbours from the old board.
2. Apply the four rules to the same snapshot.
3. Store a marker for each change; old states survive.
4. A second pass writes the final zeros and ones.

• Counting the live neighbours of every cell from the old board is step one.
• Step three marks changes with sentinel values so old states survive.

Worked example

Take a four-row, three-column board, which is Example 1 of the problem statement: [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]. The script reproduces the expected next board [[0,0,0],[1,0,1],[0,1,1],[0,1,0]].¹

Read two cells by hand. The live cell in row 2, column 0 has one live neighbour, so it dies of under-population and receives marker 2. The dead cell in row 1, column 1 has five live neighbours, more than the three a birth needs, so it stays dead.¹

A cell changes only if it is live with fewer than two or more than three neighbours, or dead with exactly three. In the sample, two live cells have one neighbour and die, and two dead cells have three and are born; every other cell keeps its state.¹ Across the twelve cells, three cells have one live neighbour, four have two, four have three, and one has five.

Text description of the diagram

• Three cells have one live neighbour and four cells have two live neighbours.
• Four cells have three live neighbours and one cell has five live neighbours.

The last row is a smaller demonstration. On an otherwise empty three by three board, a horizontal row of three live cells becomes a vertical column after one step: the two end cells die, the middle survives, and the cells above and below the middle are born. One more step gives the row back.¹

The size limits make the cost concrete. One mirror of the problem gives the constraints as 1 <= m, n <= 25, so a board holds at most 625 cells and one generation does at most 5,000 neighbour checks. A copied board would add another 625 cells of memory, and the in-place version adds none.¹

Trade-offs and edge cases

The three common designs differ in where the old state lives. Copying the board needs extra memory proportional to the board size. Sentinel values and the bit trick need only constant extra space. In the bit version, bit zero holds the current state and bit one holds the next state, and a final right shift by one promotes the next state; the script confirms it gives the same board.¹ The sentinel version is easier to explain aloud; the bit version is shorter once you know it.

Text description of the diagram

• Copying the board needs extra memory proportional to the board size.
• Sentinel values and the bit trick need only constant extra space.

Borders. An array has edges; the game does not. Treating everything outside the array as dead is the usual choice, as in Step 1. If the interviewer wants the grid to wrap around, use modular indexing for the row and column instead.

Infinite boards. The real game runs on an infinite grid (Wikipedia). The follow-up on a problem mirror says that in principle the board is infinite, which would cause problems when the active area encroaches upon the border of the array. The usual answer stores only live cells, as a set of coordinates, and tallies neighbours with a counting dictionary such as undefined. Work then grows with the number of live cells rather than the board area.

Parallel work. Each cell reads only the old board, so the cell decisions are independent when you write to a separate board; the parallel processing page covers why that matters. The in-place version can also be split across workers, but it needs a barrier between the marking pass and the finalising pass.

Why these rules. Scholarpedia says Conway chose the rules to satisfy criteria from Gardner's 1970 column, such as no starting pattern with a simple proof that the population can grow without limit. The game is also rich: a recent arXiv paper states that it "can model universal computation on Turing's machine".

How to answer it in an interview

The spoken structure: say the simultaneous-update rule, then the marker trick, then the cost, then the infinite-board answer.

Common mistakes

• "I update each cell as soon as I know its next state." (wrong) Later cells then read new values as old ones. (right) "I keep the old state readable until every cell has been judged."
• "A dead cell with two or three neighbours is born." (wrong) Two or three is the survival rule for live cells. (right) "A birth needs exactly three live neighbours."
• "I count nine cells around each cell." (wrong) That includes the cell itself. (right) "There are eight neighbours, and the cell is excluded."
• "After marking, I count neighbours equal to 1." (wrong) That misses cells marked 2, which were live. (right) "I count values above zero as live in the old board."
• "The board is exactly the game." (wrong) The game is infinite; the array is a window. (right) "I state my border assumption out loud."

Follow-up questions

How do you solve the Game of Life problem without extra space?

Use sentinel markers for cells that will change, count neighbours with the rule "above zero was live", then convert markers in a second pass. Every cell is visited twice and no second board exists.

What if the board is infinite?

Keep a set of live-cell coordinates. For each live cell, add one to a counter for each of its eight neighbours, then apply the rules to the cells in the counter. Dead cells far from any live cell never appear.

Can you use bits instead of sentinel values?

Yes. Keep the current state in bit zero and the next state in bit one, count neighbours with board[r][c] & 1, and shift every cell right by one at the end. The idea is the same as the markers.

What is the time and space complexity of Game of Life?

One generation costs O(m×n) time because each cell checks eight neighbours. The in-place version uses O(1) extra space, while a copied board uses O(m×n).

What if the grid wraps around its edges?

Replace the bounds check with modular indexing, (i + di) % m and (j + dj) % n. In Python, % with a negative left operand already wraps correctly; in C or Java use (i + di + m) % m. The rest of the solution is unchanged. To stop a simulation once nothing changes, compare two boards with the identical matrices check; for another array problem with a different pattern, see merge intervals, a sort-and-sweep problem.

Sources

1. Game of Life (problem 289) — LeetCode, 26 Oct 2026
2. Conway's Game of Life — Wikipedia, 25 Oct 2026
3. Conway's Game of Life — LifeWiki, 26 Oct 2026
4. Game of Life — Scholarpedia, 26 Oct 2026
5. The fantastic combinations of John Conway's new solitaire game life (Gardner, Scientific American, October 1970) — Wikidata record, 1 Oct 1970
6. Conway's Game of Life and universal computation (arXiv 2503.19869) — arXiv, 25 Mar 2025
7. LeetCode 289 Game of Life (in-place marking and the infinite-board follow-up) — leetcode.ca, 14 Sep 2016
8. LeetCode 289 constraints and sparse-board note — shineboy2013, 24 Dec 2021