MediumArrayMatrixSimulationUpdated Sep 2026

289. Game of Life

Asked at Adobe

Difficulty

Medium

Time

O(m * n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given a grid of cells, where each cell is either alive (1) or dead (0). Every cell looks at its eight neighbors — the cells directly left, right, up, down, and the four diagonals.

Four rules decide the next state of each cell:

  • A live cell with fewer than 2 live neighbors dies (too lonely).
  • A live cell with 2 or 3 live neighbors stays alive.
  • A live cell with more than 3 live neighbors dies (too crowded).
  • A dead cell with exactly 3 live neighbors becomes alive.

All cells change at the same time. A cell's next state depends only on the current board, never on cells that already changed in this round. Update the board in place to show the next generation. You do not return anything — just modify the given grid.

Each cell counts its 8 neighbors

board010001111000Orange cell (0,1) is alive but has only 1 liveneighbor, so it dies. Green cell (1,0) is dead but hasexactly 3 live neighbors, so it is born.
A cell's next state depends only on the current board, and all cells change at the same time.

Constraints

  • ●m == board.length
  • ●n == board[i].length
  • ●1 <= m, n <= 25
  • ●board[i][j] is 0 or 1

Examples

Example 1
Inputboard = [[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]]
WhyCell (0,1) is alive but has only 1 live neighbor, so it dies. Cell (1,0) is dead but touches exactly 3 live cells, so it is born. Cell (2,1) is alive with 3 live neighbors, so it survives.
Example 2
Inputboard = [[1,1],[1,0]]
Output[[1,1],[1,1]]
WhyThe three live cells each have 2 live neighbors, so they all survive. The dead cell at (1,1) touches all 3 live cells, so it becomes alive. Every cell ends up alive.

Asked At

1 companies
CompanyDifficulty
AdobeMediumView all Adobe questions →

How to Think About It

1

Brute force: Copy the entire board, then compute each cell's next state from the copy.

2

Optimization: Avoid the O(mn) extra space by encoding transitions in-place with bit manipulation.

3

Use values 2 and -1 as temporary markers: 0 → 1 becomes 2, 1 → 0 becomes -1.

4

After marking all transitions, sweep the board again to replace 2 with 1 and -1 with 0.

5

Optimal: Single pass in-place with O(1) extra space and O(mn) time.

Optimal Approach

Iterate every cell and count its live neighbors using direction vectors for all 8 adjacent cells. Instead of copying the board, encode state transitions in-place: a cell that was alive and dies gets marked -1, and a cell that was dead and becomes alive gets marked 2. After the first pass, do a second pass to resolve markers: 2 becomes 1 and -1 becomes 0. This gives O(mn) time and O(1) extra space.

Mark first, resolve later

pass 1: mark0-10202-12-1020A live cell that dies becomes -1. A dead cell that isborn becomes 2. Unchanged cells keep 0 or 1.pass 2: resolve000101010010Sweep again: -1 becomes 0 and 2 becomes 1. The boardnow holds the next generation.abs(v) == 1 → was alive-1 → alive now dead2 → dead now alive
Instead of copying the board, we store the old and new state together in one number, then clean up in a second pass.
ComplexityTime O(m * n)Space O(1)Each cell scans its 8 neighbors once, and the second sweep is another pass over the grid; only a few marker values are stored, so extra space is constant.

What Trips People Up in Real Interviews

1

Clarify whether you must update in-place or if extra space is allowed.

2

Count all 8 neighbors explicitly — don't forget diagonals.

3

Handle boundary cells carefully by clamping neighbor coordinates.

4

Walk through a 3x3 example with at least one birth and one death before coding.

5

Mention the encoding trick proactively — interviewers love space-optimized solutions.

Solution Code

O(m * n) time
class Solution:
    def gameOfLife(self, board):
        rows, cols = len(board), len(board[0])
        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        for r in range(rows):
            for c in range(cols):
                live = 0
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:
                        live += 1
                if board[r][c] == 1 and (live < 2 or live > 3):
                    board[r][c] = -1
                elif board[r][c] == 0 and live == 3:
                    board[r][c] = 2
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == -1:
                    board[r][c] = 0
                elif board[r][c] == 2:
                    board[r][c] = 1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Game of Life problem?

Implement Conway's Game of Life on an m x n grid where each cell is alive (1) or dead (0). Given the current state, compute the next state based on the four rules governing births, survival, deaths by loneliness, and deaths by overpopulation. The twist is to update the board in-place using encoding tricks to distinguish old from new states.

How do you solve Game of Life?

The optimal approach runs in O(m * n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Game of Life?

Game of Life is asked at Adobe. It is a medium difficulty problem.

What are common mistakes on Game of Life?
  • Clarify whether you must update in-place or if extra space is allowed.
  • Count all 8 neighbors explicitly — don't forget diagonals.
  • Handle boundary cells carefully by clamping neighbor coordinates.
  • Walk through a 3x3 example with at least one birth and one death before coding.
  • Mention the encoding trick proactively — interviewers love space-optimized solutions.