289. Game of Life - Solution

Q: Is Game of Life easy or hard?

Game of Life is generally considered a medium difficulty problem. The rules themselves are simple, but implementing them correctly while avoiding state corruption during iteration requires careful handling of neighbor checks and update order.

Q: How to solve Game of Life in O(m*n)?

Iterate through each cell of the grid and count the eight neighboring cells that are alive. Apply the Game of Life rules to determine whether the cell survives, dies, or becomes alive. Using in-place encoding (like -1 and 2) preserves original states during the first pass and allows the board to be finalized in a second pass.

Q: What is the best approach for Game of Life?

The best approach uses an in-place state transition technique. Instead of allocating another grid, the algorithm encodes temporary states such as -1 (alive to dead) and 2 (dead to alive). This allows you to count neighbors using the original state while updating cells in the same board. The result runs in O(m*n) time with O(1) extra space.

Q: What data structure is used in Game of Life?

The primary data structure is a 2D grid (matrix) implemented as a 2D array or list of lists. Algorithms iterate over the matrix and check the eight surrounding neighbors for each cell. Some implementations also use direction arrays to simplify neighbor traversal.

Q: What is the time complexity of Game of Life?

Game of Life runs in O(m*n) time because every cell in the grid must be processed once. For each cell, the algorithm checks up to eight neighbors, which is constant work. Both the extra-space solution and the in-place optimized solution have the same time complexity.

Q: Game of Life Python or Java solution approach?

Python and Java implementations typically iterate through the grid and count neighbors using direction vectors for the eight positions. The optimal implementation uses in-place markers like -1 and 2 to track state transitions. Both languages achieve O(m*n) time complexity and O(1) extra space with this approach.

Q: Is Game of Life asked at Google, Amazon, or Meta interviews?

Game of Life appears in technical interview preparation lists and is sometimes used by companies like Google, Amazon, and Meta to test matrix traversal and simulation skills. The problem evaluates how well candidates handle state transitions, neighbor scanning, and in-place updates.

The problem

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 (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously.

Given the current state of the board, update the board to reflect its next state.

Note that you do not need to return anything.

Example 1:

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]]

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

Constraints:

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

Follow up:

Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?

Approach overview

Problem Overview: You are given an m x n grid representing Conway’s Game of Life where each cell is either alive (1) or dead (0). Every cell updates simultaneously based on the number of live neighbors among the eight surrounding cells. The challenge is computing the next state of the board without corrupting neighbor calculations while you iterate through the grid.

Approach 1: Naive Approach with Extra Space (O(m*n) time, O(m*n) space)

Iterate through the grid and count the eight neighbors for each cell. Instead of updating the board immediately, store the next state in a separate m x n matrix. For each cell: if it is alive and has fewer than 2 or more than 3 live neighbors, it dies; if it has exactly 2 or 3 neighbors, it survives; a dead cell with exactly 3 neighbors becomes alive. After processing every cell, copy the new matrix back into the original board. This approach is straightforward and mirrors the rules directly, making it useful when clarity matters more than memory efficiency.

The main downside is the extra memory allocation. The algorithm still touches each cell once and checks up to eight neighbors, so the time complexity remains O(m*n). Space complexity is also O(m*n) due to the additional board. Problems like this commonly appear in array and matrix traversal scenarios where state must not be overwritten during iteration.

Approach 2: In-Place State Transition (O(m*n) time, O(1) space)

The optimal solution modifies the board in-place by encoding both the old and new states inside the same cell. While scanning the grid, mark transitional states instead of immediately overwriting values. A common encoding strategy uses:

-1 for a cell that was alive but becomes dead, and 2 for a cell that was dead but becomes alive. When counting neighbors, treat values 1 and -1 as originally alive because they represent cells that were alive before the update.

First pass: iterate through the grid, count neighbors, and assign transitional markers according to the Game of Life rules. Second pass: normalize the board by converting all positive values to 1 and all others to 0. Because transitional values preserve the previous state, neighbor counts remain correct even after partial updates.

This technique is a classic simulation pattern where temporary state encoding avoids extra memory. The board is still processed once, giving O(m*n) time complexity, while space complexity drops to O(1).

Recommended for interviews: Interviewers typically expect the in-place transition approach. The extra-space version demonstrates you understand the Game of Life rules and grid traversal, but the in-place encoding shows stronger problem-solving skills and awareness of memory optimization patterns commonly used in matrix simulations.

Approach 1: Naive Approach with Extra Space

This approach creates a copy of the original board. It calculates the new state for each cell using the current state from the original board while updating the new state in the copy. Once all cells have been processed, it updates the original board with the calculated states from the copy.

Python

def gameOfLife(board):
    m, n = len(board), len(board[0])
    copy = [[board[i][j] for j in range(n)] for i in range(m)]
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    for i in range(m):
        for j in range(n):
            live_neighbors = 0
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and copy[ni][nj] == 1:
                    live_neighbors += 1

            if copy[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                board[i][j] = 0
            elif copy[i][j] == 0 and live_neighbors == 3:
                board[i][j] = 1

Java

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[][] copy = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                copy[i][j] = board[i][j];
            }
        }

        int[] directions = {-1, 0, 1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;
                for (int dx : directions) {
                    for (int dy : directions) {
                        if (dx == 0 && dy == 0) continue;
                        int ni = i + dx, nj = j + dy;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] == 1) {
                            liveNeighbors++;
                        }
                    }
                }

                if (copy[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[i][j] = 0;
                } else if (copy[i][j] == 0 && liveNeighbors == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
}

C++

#include <vector>
using namespace std;

void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    vector<vector<int>> copy = board;
    vector<pair<int, int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = 0;
            for (auto d : directions) {
                int ni = i + d.first, nj = j + d.second;
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] == 1) {
                    liveNeighbors++;
                }
            }

            if (copy[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 0;
            } else if (copy[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = 1;
            }
        }
    }
}

JavaScript

var gameOfLife = function(board) {
    const m = board.length, n = board[0].length;
    const copy = board.map(arr => arr.slice());

    const directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let liveNeighbors = 0;
            for (const [di, dj] of directions) {
                const ni = i + di, nj = j + dj;
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] === 1) {
                    liveNeighbors++;
                }
            }

            if (copy[i][j] === 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 0;
            } else if (copy[i][j] === 0 && liveNeighbors === 3) {
                board[i][j] = 1;
            }
        }
    }
};

#include <stdio.h>
#include <stdlib.h>

void gameOfLife(int** board, int boardSize, int* boardColSize) {
    int m = boardSize;
    int n = *boardColSize;

    // Copy of the board
    int** copy = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        copy[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            copy[i][j] = board[i][j];
        }
    }

    // Directions for neighbors
    int directions[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = 0;
            for (int d = 0; d < 8; d++) {
                int ni = i + directions[d][0];
                int nj = j + directions[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] == 1) {
                    liveNeighbors++;
                }
            }

            if (copy[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 0;
            } else if (copy[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        free(copy[i]);
    }
    free(copy);
}

public class Solution {
    public void GameOfLife(int[][] board) {
        int m = board.Length, n = board[0].Length;
        int[][] copy = new int[m][];
        for (int i = 0; i < m; i++) {
            copy[i] = new int[n];
            for (int j = 0; j < n; j++) {
                copy[i][j] = board[i][j];
            }
        }

        int[] directions = {-1, 0, 1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;
                foreach (int dx in directions) {
                    foreach (int dy in directions) {
                        if (dx == 0 && dy == 0) continue;
                        int ni = i + dx, nj = j + dy;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] == 1) {
                            liveNeighbors++;
                        }
                    }
                }

                if (copy[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
                    board[i][j] = 0;
                else if (copy[i][j] == 0 && liveNeighbors == 3)
                    board[i][j] = 1;
            }
        }
    }
}

This Python solution copies the board to a new list called 'copy' using list comprehensions. It then iterates through each cell and counts its live neighbors. The Game of Life rules are applied to determine the new state for each cell, which is reflected in the original board.

Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n), due to the board copying.

Try this approach in the editor

Approach 2: In-Place State Transition Approach

This approach uses in-place updates by leveraging different state values. We introduce temporary states: 2 represents a cell that was originally live (1) but will be dead in the next state, and -1 represents a cell that was dead (0) but will be live in the next state. At the end, these temporary states are converted to the final states.

Python

def gameOfLife(board):
    m, n = len(board), len(board[0])
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    for i in range(m):
        for j in range(n):
            live_neighbors = 0
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and abs(board[ni][nj]) == 1:
                    live_neighbors += 1

            if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                board[i][j] = 2
            elif board[i][j] == 0 and live_neighbors == 3:
                board[i][j] = -1

    for i in range(m):
        for j in range(n):
            if board[i][j] == -1:
                board[i][j] = 1
            elif board[i][j] == 2:
                board[i][j] = 0

Java

class Solution {
    public void gameOfLife(int[][] board) {
        int[] directions = {-1, 0, 1};
        int m = board.length, n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;
                for (int dx : directions) {
                    for (int dy : directions) {
                        if (dx == 0 && dy == 0) continue;
                        int ni = i + dx, nj = j + dy;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && Math.abs(board[ni][nj]) == 1) {
                            liveNeighbors++;
                        }
                    }
                }

                if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[i][j] = 2;
                }
                if (board[i][j] == 0 && liveNeighbors == 3) {
                    board[i][j] = -1;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == -1) {
                    board[i][j] = 1;
                } else if (board[i][j] == 2) {
                    board[i][j] = 0;
                }
            }
        }
    }
}

C++

#include <vector>
using namespace std;

void gameOfLife(vector<vector<int>>& board) {
    vector<pair<int, int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    int m = board.size(), n = board[0].size();

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = 0;
            for (auto& [dx, dy] : directions) {
                int ni = i + dx, nj = j + dy;
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && abs(board[ni][nj]) == 1) {
                    liveNeighbors++;
                }
            }

            if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 2;
            } else if (board[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = -1;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == -1) {
                board[i][j] = 1;
            } else if (board[i][j] == 2) {
                board[i][j] = 0;
            }
        }
    }
}

JavaScript

var gameOfLife = function(board) {
    let m = board.length, n = board[0].length;
    const directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let liveNeighbors = 0;
            for (const [di, dj] of directions) {
                const ni = i + di, nj = j + dj;
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && Math.abs(board[ni][nj]) == 1) {
                    liveNeighbors++;
                }
            }

            if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 2;
            } else if (board[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = -1;
            }
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] == -1) {
                board[i][j] = 1;
            } else if (board[i][j] == 2) {
                board[i][j] = 0;
            }
        }
    }
};

#include <stdio.h>

void gameOfLife(int** board, int boardSize, int* boardColSize) {
    int directions[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    int m = boardSize;
    int n = *boardColSize;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = 0;
            for (int d = 0; d < 8; d++) {
                int ni = i + directions[d][0];
                int nj = j + directions[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && abs(board[ni][nj]) == 1) {
                    liveNeighbors++;
                }
            }

            if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 2;
            } else if (board[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = -1;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == -1) {
                board[i][j] = 1;
            } else if (board[i][j] == 2) {
                board[i][j] = 0;
            }
        }
    }
}

public class Solution {
    public void GameOfLife(int[][] board) {
        int m = board.Length, n = board[0].Length;
        int[] directions = {-1, 0, 1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;
                foreach (int dx in directions) {
                    foreach (int dy in directions) {
                        if (dx == 0 && dy == 0) continue;
                        int ni = i + dx, nj = j + dy;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && Math.Abs(board[ni][nj]) == 1) {
                            liveNeighbors++;
                        }
                    }
                }

                if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
                    board[i][j] = 2;
                else if (board[i][j] == 0 && liveNeighbors == 3)
                    board[i][j] = -1;
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == -1) {
                    board[i][j] = 1;
                } else if (board[i][j] == 2) {
                    board[i][j] = 0;
                }
            }
        }
    }
}

The Python in-place solution identifies transition states to save space by indicating transitions using preset positive-negative variations, retaining pre-existing indexed validation with a single final transformation pass.

Complexity

Time Complexity: O(m * n), covers entire plane uniformly.
Space Complexity: O(1), owing to nil reliance on additional heuristic buffers.

Try this approach in the editor

Approach 3: In-place marking

Let's define two new states. State 2 indicates that the living cell becomes dead in the next state, and state -1 indicates that the dead cell becomes alive in the next state. Therefore, for the current grid we are traversing, if the grid is greater than 0, it means that the current grid is a living cell, otherwise it is a dead cell.

So we can traverse the entire board, for each grid, count the number of living neighbors around the grid, and use the variable live to represent it. If the current grid is a living cell, then when live \lt 2 or live \gt 3, the next state of the current grid is a dead cell, that is, state 2; if the current grid is a dead cell, then when live = 3, the next state of the current grid is an active cell, that is, state -1.

Finally, we traverse the board again, and update the grid with state 2 to a dead cell, and update the grid with state -1 to an active cell.

The time complexity is O(m times n), where m and n are the number of rows and columns of the board, respectively. We need to traverse the entire board. And the space complexity is O(1).

TypeScript

/**
 Do not return anything, modify board in-place instead.
 */
function gameOfLife(board: number[][]): void {
    const m = board.length;
    const n = board[0].length;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let live = -board[i][j];
            for (let x = i - 1; x <= i + 1; ++x) {
                for (let y = j - 1; y <= j + 1; ++y) {
                    if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] > 0) {
                        ++live;
                    }
                }
            }
            if (board[i][j] === 1 && (live < 2 || live > 3)) {
                board[i][j] = 2;
            }
            if (board[i][j] === 0 && live === 3) {
                board[i][j] = -1;
            }
        }
    }
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (board[i][j] === 2) {
                board[i][j] = 0;
            }
            if (board[i][j] === -1) {
                board[i][j] = 1;
            }
        }
    }
}

func gameOfLife(board [][]int) {
	m, n := len(board), len(board[0])
	for i := 0; i < m; i++ {
		for j, v := range board[i] {
			live := -v
			for x := i - 1; x <= i+1; x++ {
				for y := j - 1; y <= j+1; y++ {
					if x >= 0 && x < m && y >= 0 && y < n && board[x][y] > 0 {
						live++
					}
				}
			}
			if v == 1 && (live < 2 || live > 3) {
				board[i][j] = 2
			}
			if v == 0 && live == 3 {
				board[i][j] = -1
			}
		}
	}
	for i := 0; i < m; i++ {
		for j, v := range board[i] {
			if v == 2 {
				board[i][j] = 0
			}
			if v == -1 {
				board[i][j] = 1
			}
		}
	}
}

Rust

const DIR: [(i32, i32); 8] = [
    (-1, 0),
    (1, 0),
    (0, -1),
    (0, 1),
    (-1, -1),
    (-1, 1),
    (1, -1),
    (1, 1),
];

impl Solution {
    #[allow(dead_code)]
    pub fn game_of_life(board: &mut Vec<Vec<i32>>) {
        let n = board.len();
        let m = board[0].len();
        let mut weight_vec: Vec<Vec<i32>> = vec![vec![0; m]; n];

        // Initialize the weight vector
        for i in 0..n {
            for j in 0..m {
                if board[i][j] == 0 {
                    continue;
                }
                for (dx, dy) in DIR {
                    let x = (i as i32) + dx;
                    let y = (j as i32) + dy;
                    if Self::check_bounds(x, y, n as i32, m as i32) {
                        weight_vec[x as usize][y as usize] += 1;
                    }
                }
            }
        }

        // Update the board
        for i in 0..n {
            for j in 0..m {
                if weight_vec[i][j] < 2 {
                    board[i][j] = 0;
                } else if weight_vec[i][j] <= 3 {
                    if board[i][j] == 0 && weight_vec[i][j] == 3 {
                        board[i][j] = 1;
                    }
                } else {
                    board[i][j] = 0;
                }
            }
        }
    }

    #[allow(dead_code)]
    fn check_bounds(i: i32, j: i32, n: i32, m: i32) -> bool {
        i >= 0 && i < n && j >= 0 && j < m
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Naive Approach with Extra Space	Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(m * n), due to the board copying.
In-Place State Transition Approach	Time Complexity: O(m * n), covers entire plane uniformly. Space Complexity: O(1), owing to nil reliance on additional heuristic buffers.
In-place marking	–

Complexity analysis

Approach	Time	Space	When to Use
Naive Approach with Extra Space	O(m*n)	O(m*n)	Best for clarity and quick implementation when memory usage is not constrained
In-Place State Transition	O(m*n)	O(1)	Preferred in interviews and production when memory efficiency matters

Frequently asked questions

Is Game of Life easy or hard?

Game of Life is generally considered a medium difficulty problem. The rules themselves are simple, but implementing them correctly while avoiding state corruption during iteration requires careful handling of neighbor checks and update order.

How to solve Game of Life in O(m*n)?

Iterate through each cell of the grid and count the eight neighboring cells that are alive. Apply the Game of Life rules to determine whether the cell survives, dies, or becomes alive. Using in-place encoding (like -1 and 2) preserves original states during the first pass and allows the board to be finalized in a second pass.

What is the best approach for Game of Life?

The best approach uses an in-place state transition technique. Instead of allocating another grid, the algorithm encodes temporary states such as -1 (alive to dead) and 2 (dead to alive). This allows you to count neighbors using the original state while updating cells in the same board. The result runs in O(m*n) time with O(1) extra space.

What data structure is used in Game of Life?

The primary data structure is a 2D grid (matrix) implemented as a 2D array or list of lists. Algorithms iterate over the matrix and check the eight surrounding neighbors for each cell. Some implementations also use direction arrays to simplify neighbor traversal.

What is the time complexity of Game of Life?

Game of Life runs in O(m*n) time because every cell in the grid must be processed once. For each cell, the algorithm checks up to eight neighbors, which is constant work. Both the extra-space solution and the in-place optimized solution have the same time complexity.

Game of Life Python or Java solution approach?

Python and Java implementations typically iterate through the grid and count neighbors using direction vectors for the eight positions. The optimal implementation uses in-place markers like -1 and 2 to track state transitions. Both languages achieve O(m*n) time complexity and O(1) extra space with this approach.

Is Game of Life asked at Google, Amazon, or Meta interviews?

Game of Life appears in technical interview preparation lists and is sometimes used by companies like Google, Amazon, and Meta to test matrix traversal and simulation skills. The problem evaluates how well candidates handle state transitions, neighbor scanning, and in-place updates.

Game of Life solution and explanation

The problem

Approach overview

Approach 1: Naive Approach with Extra Space

Approach 2: In-Place State Transition Approach

Approach 3: In-place marking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Game of Life solution and explanation

The problem

Approach overview

Approach 1: Naive Approach with Extra Space

Approach 2: In-Place State Transition Approach

Approach 3: In-place marking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems