Game of Life - Video Solutions

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.