We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Game of Life

Difficulty: Medium

Problem Description

The Game of Life is a cellular automaton where each cell in an m x n grid has an initial state: live (1) or dead (0). The next state of the board is determined by applying specific rules based on the current state of each cell and its eight neighbors. The challenge is to update the board to reflect its next state simultaneously without returning anything.

Key Insights

  • Each cell interacts with its eight neighbors, and its next state is determined by the number of live neighbors.
  • There are four rules to determine whether a cell will live, die, or be born in the next generation.
  • The update must be done simultaneously, meaning the current state should not be modified until all calculations are complete.
  • We can use a two-pass approach: mark future states temporarily without altering the original states.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1) (In-place modification)

Solution

To solve the problem, we will use a 2D array to represent the board. We will iterate through each cell and count its live neighbors. Based on the count, we will determine the future state of each cell using temporary markers (e.g., using values like 2 for live cells that will die and 3 for dead cells that will become live). After processing all cells, we will convert these temporary markers back to the final states (0 or 1).

Code Solutions

def gameOfLife(board):
    if not board or not board[0]:
        return
    
    m, n = len(board), len(board[0])
    
    # Directions for the 8 neighbors
    directions = [(-1, -1), (-1, 0), (-1, 1), 
                  (0, -1),         (0, 1), 
                  (1, -1), (1, 0), (1, 1)]
    
    # First pass: Count neighbors
    for i in range(m):
        for j in range(n):
            live_neighbors = 0
            for dx, dy in directions:
                ni, nj = i + dx, j + dy
                if 0 <= ni < m and 0 <= nj < n and abs(board[ni][nj]) == 1:
                    live_neighbors += 1
            
            # Apply rules
            if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                board[i][j] = -1  # Mark as dead
            elif board[i][j] == 0 and live_neighbors == 3:
                board[i][j] = 2  # Mark as live
    
    # Second pass: Update to final state
    for i in range(m):
        for j in range(n):
            if board[i][j] > 0:
                board[i][j] = 1  # Live
            else:
                board[i][j] = 0  # Dead
← Back to All Questions