Game of Life - Practice Coding Problems

Game of Life - 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:

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: You do not need to return anything.

Input & Output

Example 1 — Standard Pattern

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

💡 Note: The bottom row [1,1,1] creates a classic 'blinker' pattern. Cell at (1,0) gets exactly 3 neighbors so becomes alive. Cell at (1,1) dies from under-population.

Example 2 — All Dead

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

› Output: [[1,1],[1,1]]

💡 Note: Top-left has 2 neighbors (survives), top-right has 2 neighbors (survives), bottom-left has 2 neighbors (survives), bottom-right has 3 neighbors (becomes alive).

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Board

Grid of live (1) and dead (0) cells

Apply Rules

Count neighbors and apply Conway's rules simultaneously

Output Board

Updated grid showing next generation

Key Takeaway

🎯 Key Insight: All cell updates must happen simultaneously based on the current state

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 10

The key insight is that all cell changes must happen simultaneously. The optimal approach uses in-place state encoding with bit manipulation to avoid extra space. Time: O(m×n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ In-Place with State Encoding	O(m×n)	O(1)	Use additional bit states to track both current and next states simultaneously
Copy Board Approach	O(m×n)	O(m×n)	Create a copy of the board to avoid interference during simultaneous updates

In-Place with State Encoding — Algorithm Steps

Step 1: For each cell, count live neighbors using current state
Step 2: Encode next state: 2 = dead→alive, 3 = alive→alive
Step 3: Convert all cells back to 0/1 by taking modulo 2

Visualization

Tap to expand

Step-by-Step Walkthrough

Original State

Each cell is 0 (dead) or 1 (alive)

Encode Next State

Use 2=dead→alive, 3=alive→alive

Extract Final

Right shift by 1 to get final state

Code -

solution.c — C

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

void solution(int** board, int m, int n) {
    if (board == NULL || m == 0 || n == 0) return;
    
    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;
            
            // Count live neighbors (current state is board[ni][nj] & 1)
            for (int k = 0; k < 8; k++) {
                int ni = i + directions[k][0], nj = j + directions[k][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && (board[ni][nj] & 1) == 1) {
                    liveNeighbors++;
                }
            }
            
            // Apply Conway's rules with state encoding
            if ((board[i][j] & 1) == 1) {  // Currently alive
                if (liveNeighbors == 2 || liveNeighbors == 3) {
                    board[i][j] = 3;  // Alive -> Alive
                }
            } else {  // Currently dead
                if (liveNeighbors == 3) {
                    board[i][j] = 2;  // Dead -> Alive
                }
            }
        }
    }
    
    // Convert to final state
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
}

int main() {
    // Simple parsing for small test cases
    int m = 4, n = 3;  // Example dimensions
    int** board = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        board[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Example board initialization
    int data[4][3] = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = data[i][j];
        }
    }
    
    solution(board, m, n);
    
    // Print result
    printf("[");
    for (int i = 0; i < m; i++) {
        printf("[");
        for (int j = 0; j < n; j++) {
            printf("%d", board[i][j]);
            if (j < n - 1) printf(",");
        }
        printf("]");
        if (i < m - 1) printf(",");
    }
    printf("]\n");
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(board[i]);
    }
    free(board);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Single pass through all cells, each cell checks 8 neighbors

✓ Linear Growth

Space Complexity

O(1)

No extra data structures, only modify input board in-place

✓ Linear Space

95.0K Views

Medium Frequency

~15 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

In-Place with State Encoding — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler