Log inSign up
mediumLeetCodeNot Started

Game of Life

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

The board is made up of an m x n grid of cells, where each cell has an initial state: live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules:

1. Underpopulation: Any live cell with fewer than two live neighbors dies. 2. Survival: Any live cell with two or three live neighbors lives on to the next generation. 3. Overpopulation: Any live cell with more than three live neighbors dies. 4. Reproduction: Any dead cell with exactly three live neighbors becomes a live cell.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Given the current state of the m x n grid board, update the board to reflect its next state in-place.

Example 1 · Standard 4x3 Grid Update:

Input: board = [[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: Simultaneous application of the 4 Conway rules transitions the board to its next generation.

Example 2 · 2x2 Stable Block Grid:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]
Explanation: The dead cell (1,1) has 3 live neighbors and reproduces to become 1. All live cells have 2 live neighbors and survive.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D matrix coordinate navigation and boundary checks
  • 8-directional neighbor offsetting
  • Basic bit manipulation (AND, OR, bit shift) or state encoding

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master simultaneous cellular automata simulation.
  • Learn the 2-bit state packing pattern to achieve in-place O(1) memory.
  • Safely implement 8-directional neighbor counting with boundary validation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Simultaneous state updates across a grid/array.
  • Input is binary (0 or 1), leaving higher-order integer bits unused.
  • In-place O(1) auxiliary space constraint.

Algorithmic Decision Tree:

  • Use bitmasking: Store next_state << 1 | current_state.
  • Alternatively, use transition markers: 0->0 as 0, 1->1 as 1, 1->0 as -1 (or 2), 0->1 as 2 (or 3).

Connected Patterns:

Set Matrix ZeroesRotate Image01 Matrix

1. Copy Grid Simulation (Brute Force)

Intuition

Rules: 1. Any live cell with < 2 live neighbors dies. 2. Any live cell with 2 or 3 live neighbors lives. 3. Any live cell with > 3 live neighbors dies. 4. Any dead cell with exactly 3 live neighbors becomes live. Read neighbor counts from copy and write next state to board.

When to apply: Use to verify Conway's game rules without state contamination.

Copy Grid Next State Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0]
Current operationSTEP 1 OF 6
Glider sub-pattern: live cells at (0,1), (1,2), (2,0), (2,1), (2,2)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
0
↑ Scan
1
0
r1
0
0
1
r2
1
1
1
r3
0
0
0
Variables at this step
liveCount
5
Check / comparison
Evaluate 8 neighbors for every cell.
Decision / next transition
Begin evolution scan.
Why this step matters

Glider sub-pattern: live cells at (0,1), (1,2), (2,0), (2,1), (2,2). Copy created.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void gameOfLife(int[][] board) {
6 int m = board.length, n = board[0].length;
7 int[][] copy = new int[m][n];
8 for (int r = 0; r < m; r++) {
9 for (int c = 0; c < n; c++) copy[r][c] = board[r][c];
10 }
11
12 int[] dirs = {-1, 0, 1};
13 for (int r = 0; r < m; r++) {
14 for (int c = 0; c < n; c++) {
15 int liveNeighbors = 0;
16 for (int i = 0; i < 3; i++) {
17 for (int j = 0; j < 3; j++) {
18 if (dirs[i] == 0 && dirs[j] == 0) continue;
19 int nr = r + dirs[i], nc = c + dirs[j];
20 if (nr >= 0 && nr < m && nc >= 0 && nc < n && copy[nr][nc] == 1) {
21 liveNeighbors++;
22 }
23 }
24 }
25
26 if (copy[r][c] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
27 board[r][c] = 0;
28 } else if (copy[r][c] == 0 && liveNeighbors == 3) {
29 board[r][c] = 1;
30 }
31 }
32 }
33 }
34 }
35
36 public static void main(String[] args) {
37 Solution sol = new Solution();
38 int[][] board = {
39 {0, 1, 0},
40 {0, 0, 1},
41 {1, 1, 1},
42 {0, 0, 0}
43 };
44 sol.gameOfLife(board);
45 System.out.println("Next Gen: " + Arrays.deepToString(board));
46 }
47}

Time & Space Complexity

  • Time complexity: O(m * n) — Count neighbors for each of m*n cells in 8 directions.
  • Space complexity: O(m * n) — O(m * n) auxiliary board copy.

Why Brute Force Doesn't Scale:

For large grid simulations, duplicating memory causes unnecessary cache misses and garbage collection overhead.

2-bit encoding reduces space complexity from O(M * N) to O(1) with 0 memory allocations.

2. State Transition Codes (-1 and 2)

Intuition

Since cells can be read after previous cells are modified, mark transitions: if a live cell (1) dies, set it to -1 (abs(-1) == 1 indicates it was previously live). If a dead cell (0) becomes live, set it to 2 (abs(2) != 1 indicates it was previously dead). In a second pass, convert -1 to 0 and 2 to 1.

When to apply: Use to achieve in-place mutation without bit manipulation.

State Transition Code Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0]
Current operationSTEP 1 OF 6
Board: 4x3 grid
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
0
-1
↑ 1->0 marked -1
0
r1
0
0
1
r2
1
1
1
r3
0
0
0
Variables at this step
board[0][1]
-1
Check / comparison
Inspect cell (0,1)=1.
Decision / next transition
1 has only 1 live neighbor. Dies: mark board[0][1] = -1.
Why this step matters

Board: 4x3 grid. Any cell with value 1 or -1 counts as previously live.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void gameOfLife(int[][] board) {
6 int m = board.length, n = board[0].length;
7 int[] dirs = {-1, 0, 1};
8
9 for (int r = 0; r < m; r++) {
10 for (int c = 0; c < n; c++) {
11 int live = 0;
12 for (int dr : dirs) {
13 for (int dc : dirs) {
14 if (dr == 0 && dc == 0) continue;
15 int nr = r + dr, nc = c + dc;
16 if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
17 if (Math.abs(board[nr][nc]) == 1) live++;
18 }
19 }
20 }
21
22 if (board[r][c] == 1 && (live < 2 || live > 3)) {
23 board[r][c] = -1; // 1 -> 0
24 } else if (board[r][c] == 0 && live == 3) {
25 board[r][c] = 2; // 0 -> 1
26 }
27 }
28 }
29
30 for (int r = 0; r < m; r++) {
31 for (int c = 0; c < n; c++) {
32 if (board[r][c] > 0) board[r][c] = 1;
33 else board[r][c] = 0;
34 }
35 }
36 }
37 }
38
39 public static void main(String[] args) {
40 Solution sol = new Solution();
41 int[][] board = {
42 {0, 1, 0},
43 {0, 0, 1},
44 {1, 1, 1},
45 {0, 0, 0}
46 };
47 sol.gameOfLife(board);
48 System.out.println("Next Gen: " + Arrays.deepToString(board));
49 }
50}

Time & Space Complexity

  • Time complexity: O(m * n) — Two passes across m*n cells with O(1) neighbor lookups.
  • Space complexity: O(1) — All state transitions stored directly within the original board.

3. 2-Bit State Encoding (Optimal & Standard)

Intuition

1. For each cell: count live neighbors using (board[nr][nc] & 1). 2. If cell stays live or becomes live, set the 2nd bit: board[r][c] |= 2. 3. Final pass: shift right by 1 (board[r][c] >>= 1) to transition all cells to next state simultaneously.

When to apply: Use as the gold-standard bitwise technique for 2-state concurrent cellular automata.

2-Bit State Encoding Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0]
Current operationSTEP 1 OF 6
Bit 0 = current state
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
0
1
↑ 01
0
r1
0
0
1
r2
1
1
1
r3
0
0
0
Variables at this step
board[0][1]
01 (past=1, next=0)
Check / comparison
Cell (0,1)=1 (binary 01).
Decision / next transition
Live neighbors = 1. Dies: bit 1 remains 0 (binary 01 = 1).
Why this step matters

Bit 0 = current state. Bit 1 = next state. Read past state with (val & 1).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void gameOfLife(int[][] board) {
6 int m = board.length, n = board[0].length;
7 int[] dirs = {-1, 0, 1};
8
9 for (int r = 0; r < m; r++) {
10 for (int c = 0; c < n; c++) {
11 int live = 0;
12 for (int dr : dirs) {
13 for (int dc : dirs) {
14 if (dr == 0 && dc == 0) continue;
15 int nr = r + dr, nc = c + dc;
16 if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
17 if ((board[nr][nc] & 1) == 1) live++;
18 }
19 }
20 }
21
22 if ((board[r][c] & 1) == 1) {
23 if (live == 2 || live == 3) board[r][c] |= 2;
24 } else {
25 if (live == 3) board[r][c] |= 2;
26 }
27 }
28 }
29
30 for (int r = 0; r < m; r++) {
31 for (int c = 0; c < n; c++) {
32 board[r][c] >>= 1;
33 }
34 }
35 }
36 }
37
38 public static void main(String[] args) {
39 Solution sol = new Solution();
40 int[][] board = {
41 {0, 1, 0},
42 {0, 0, 1},
43 {1, 1, 1},
44 {0, 0, 0}
45 };
46 sol.gameOfLife(board);
47 System.out.println("Next Gen: " + Arrays.deepToString(board));
48 }
49}

Time & Space Complexity

  • Time complexity: O(m * n) — Two simple matrix iterations; bitwise operations are O(1) primitive CPU ops.
  • Space complexity: O(1) — Strictly in-place manipulation of integer bit flags.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Matrix Clone CopyO(M * N)O(M * N)Create a deep copy of the grid. Read neighbor counts from the copy, then write new states into the original matrix.Matrix allocation and copy operations.
2.Better — State Transition Numeric FlagsO(M * N)O(1)Mark state transitions using custom integers: 2 represents live->dead, -1 represents dead->live. Count neighbors by checking abs(board[nr][nc]) == 1 || board[nr][nc] == 2.Two passes over matrix.
3.Optimal — 2-Bit State Encoding (Bitwise Shift)OptimalO(M * N)O(1)Use bit 0 for current generation and bit 1 for next generation. Set bit 1 using board[r][c] |= 2 if cell lives. In pass 2, apply board[r][c] >>= 1 to finalize.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • 1x1 board — Cannot have >= 2 neighbors, always dies or stays dead (becomes [[0]]).
  • All dead cells — Stays all 0s throughout execution.
  • All live cells in large board — Corner cells survive/die according to local density.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether in-place mutation of the input matrix is required or if a cloned buffer is permissible.
  2. Explain the 2-bit state packing technique clearly before writing code, noting bit 0 = present and bit 1 = future.
  3. Discuss how to scale to an infinite board (e.g. sparse Hash Set of live coordinates).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Game of Life?

2.Why is the brute force approach suboptimal for large inputs in Game of Life?

3.Which data structure or technique enables the optimal solution for Game of Life?

Back to DSA Sheet