Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

289. Game of Life - Leetcode Solution

Code Implementation

class Solution:
    def gameOfLife(self, board):
        """
        Do not return anything, modify board in-place instead.
        """
        rows, cols = len(board), len(board[0])
        directions = [(-1, -1), (-1, 0), (-1, 1),
                      (0, -1),         (0, 1),
                      (1, -1), (1, 0), (1, 1)]
        
        for r in range(rows):
            for c in range(cols):
                live_neighbors = 0
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        if board[nr][nc] == 1 or board[nr][nc] == -1:
                            live_neighbors += 1
                # Apply the rules by marking with temporary states
                if board[r][c] == 1:
                    if live_neighbors < 2 or live_neighbors > 3:
                        board[r][c] = -1  # Alive to dead
                else:
                    if live_neighbors == 3:
                        board[r][c] = 2   # Dead to alive

        # Final pass to update the board
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == -1:
                    board[r][c] = 0
                elif board[r][c] == 2:
                    board[r][c] = 1
      
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int rows = board.size(), cols = board[0].size();
        vector<pair<int, int>> dirs = {{-1,-1},{-1,0},{-1,1},
                                         {0,-1},        {0,1},
                                         {1,-1},{1,0},{1,1}};
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int live = 0;
                for (auto [dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                        if (board[nr][nc] == 1 || board[nr][nc] == -1)
                            ++live;
                    }
                }
                if (board[r][c] == 1) {
                    if (live < 2 || live > 3)
                        board[r][c] = -1;
                } else {
                    if (live == 3)
                        board[r][c] = 2;
                }
            }
        }
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (board[r][c] == -1) board[r][c] = 0;
                else if (board[r][c] == 2) board[r][c] = 1;
            }
        }
    }
};
      
class Solution {
    public void gameOfLife(int[][] board) {
        int rows = board.length, cols = board[0].length;
        int[][] dirs = {{-1,-1},{-1,0},{-1,1},
                        {0,-1},       {0,1},
                        {1,-1},{1,0},{1,1}};
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int live = 0;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                        if (board[nr][nc] == 1 || board[nr][nc] == -1)
                            live++;
                    }
                }
                if (board[r][c] == 1) {
                    if (live < 2 || live > 3)
                        board[r][c] = -1;
                } else {
                    if (live == 3)
                        board[r][c] = 2;
                }
            }
        }
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == -1)
                    board[r][c] = 0;
                else if (board[r][c] == 2)
                    board[r][c] = 1;
            }
        }
    }
}
      
var gameOfLife = function(board) {
    const rows = board.length, cols = board[0].length;
    const dirs = [[-1,-1],[-1,0],[-1,1],
                  [0,-1],       [0,1],
                  [1,-1],[1,0],[1,1]];
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            let live = 0;
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    if (board[nr][nc] === 1 || board[nr][nc] === -1)
                        live++;
                }
            }
            if (board[r][c] === 1) {
                if (live < 2 || live > 3)
                    board[r][c] = -1;
            } else {
                if (live === 3)
                    board[r][c] = 2;
            }
        }
    }
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (board[r][c] === -1)
                board[r][c] = 0;
            else if (board[r][c] === 2)
                board[r][c] = 1;
        }
    }
};

Problem Description

The "Game of Life" is a cellular automaton devised by mathematician John Conway. In this problem, you are given a 2D grid called board where each cell is either dead (0) or alive (1). The board evolves in-place according to these rules:

  • Any live cell with fewer than two live neighbors dies (underpopulation).
  • 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 (overpopulation).
  • Any dead cell with exactly three live neighbors becomes a live cell (reproduction).

The update must be done simultaneously for all cells, meaning the next state for each cell is based only on the current state of the board, not on any updates made during this turn. The task is to modify the board in-place to represent the next state after applying the rules above.

Thought Process

At first glance, it seems straightforward to create a new grid and fill it with the next state for each cell. However, the problem wants us to update the board in-place to save space.

If we update a cell directly, its new value could affect the computation of its neighbors because the update for all cells must be based on the original state. This leads us to consider how to record both the previous and next state for each cell without using extra space.

The key insight is to use temporary markers to encode both the current and the next state within the same cell value. For example, if a cell was alive but will die, we can mark it with a special value (say, -1). If a cell was dead but will become alive, we can mark it with another value (say, 2). After all updates, we do a final pass to convert these markers to the final states.

This approach lets us process the board in-place, avoids extra memory, and ensures the updates are simultaneous.

Solution Approach

  • Step 1: Define Directions
    • For each cell, we need to count live neighbors. There are 8 possible directions (horizontal, vertical, diagonal).
  • Step 2: First Pass – Mark State Transitions
    • Iterate through every cell in the board.
    • For each cell, count the number of live neighbors. When counting, treat cells marked as -1 (was alive, now dead) as alive for the purpose of neighbor counting, since their original state was alive.
    • Apply the Game of Life rules:
      • If a live cell dies, mark it as -1 (was alive, now dead).
      • If a dead cell becomes alive, mark it as 2 (was dead, now alive).
  • Step 3: Second Pass – Finalize the Board
    • Iterate through the board again.
    • Convert all -1 values to 0 (dead), and all 2 values to 1 (alive).
  • Why This Works
    • By using special markers, we preserve the original state for neighbor counting while allowing us to update the board in-place.
    • No extra space is needed beyond a few integers for directions.

Example Walkthrough

Let's walk through a simple example. Suppose the input board is: 

[
  [0, 1, 0],
  [0, 1, 0],
  [0, 1, 0]
]

For the cell at (1,1) (center), it has 2 live neighbors (above and below), so it stays alive. The cells at (0,1) and (2,1) each have only one live neighbor, so they die (underpopulation). The dead cells at (1,0) and (1,2) each have 3 live neighbors, so they become alive (reproduction).

After the first pass (with markers), the board looks like this: 

[
  [0, -1, 0],
  [2,  1, 2],
  [0, -1, 0]
]
  • -1 means the cell was alive, now dead.
  • 2 means the cell was dead, now alive.

After the second pass (finalizing): 

[
  [0, 0, 0],
  [1, 1, 1],
  [0, 0, 0]
]

This matches the expected next state of the board.

Time and Space Complexity

  • Brute-force Approach:
    • Would use O(mn) time and O(mn) space (for a copy of the board).
  • Optimized (In-place) Approach:
    • Time Complexity: O(mn), where m is the number of rows and n is the number of columns. Each cell is visited twice (once for marking, once for finalizing).
    • Space Complexity: O(1), because we use only a constant amount of extra memory for directions and temporary state markers. The board is modified in-place.

Summary

The Game of Life problem challenges us to update a grid based on neighbor states, all at once, and in-place. The elegant solution is to use special marker values to encode both the previous and next state within each cell, allowing us to perform the update without extra space. This approach leverages careful in-place mutation and a two-pass algorithm, resulting in a clean and efficient solution.