Game of Life

289.Game of Life

Array

Matrix

Simulation

Problem Statement:

Given a board with cells, play Conway's Game of Life: each cell can be alive (1) or dead (0). Each cell's next state is based on its eight neighbors:

• Live cell: survives with 2-3 live neighbors, dies otherwise
• Dead cell: becomes alive with exactly 3 live neighbors

Update board in-place to next state.

Key States:

1. 0: Dead cell
2. 1: Live cell
3. 2: Dead → Live (will become alive)
4. 3: Live → Dead (will die)

Algorithm:

1. Use states 2 and 3 to track changes in-place:
   • 2: Cell that was dead (0) becomes alive
   • 3: Cell that was alive (1) becomes dead
2. Two passes:
   • First pass: Mark changes with states 2 and 3
   • Second pass: Convert states 2→1 and 3→0
3. When counting neighbors:
   • Both 1 and 3 count as live cells
   • Check eight directions (dx, dy)

Java Solution:

public void gameOfLife(int[][] board) {
    int m = board.length;
    int n = board[0].length;
    
    // First pass: mark changes
    // 2 = dead→live, 3 = live→dead
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = neighbors(board, i, j);
            
            if (board[i][j] == 1) {
                // Live cell dies if < 2 or > 3 neighbors
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 3;    // Will die
                }
            } else if (liveNeighbors == 3) {
                // Dead cell becomes alive with exactly 3 neighbors
                board[i][j] = 2;        // Will live
            }
        }
    }
    
    recalibrateBoard(board);
}

// Count live neighbors (states 1 or 3 count as live)
private int neighbors(int[][] board, int x, int y) {
    int count = 0;
    // Check all 8 directions
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            int newX = x + dx;
            int newY = y + dy;
            // Skip if out of bounds or cell itself
            if (newX < 0 || newY < 0 || newX >= board.length || 
                newY >= board[0].length || (dx == 0 && dy == 0)) 
                continue;
                
            int cell = board[newX][newY];
            // Count 1 and 3 as live
            if (cell == 1 || cell == 3) count++;
        }
    }
    return count;
}

// Second pass: update states
// 2→1 (dead→alive), 3→0 (alive→dead)
private void recalibrateBoard(int[][] board) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 2) board[i][j] = 1;
            if (board[i][j] == 3) board[i][j] = 0;
        }
    }
}

Time & Space Complexity:

Time: O(m×n) - visit each cell twice
Space: O(1) - in-place modification using states 2 and 3