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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Game of Life

Number: 289

Difficulty: Medium

Paid? No

Companies: Amazon, Salesforce, Microsoft, Warnermedia, Meta, BitGo, Oracle, Opendoor, Adobe, Cisco, Dropbox, Google, Snap, Two Sigma

Problem Description

Given an m x n board representing the state of Conway's Game of Life where each cell is live (1) or dead (0), update the board to its next state by applying the four rules simultaneously. Changes must be made in-place without using a duplicate board.

Key Insights

  • The update must happen simultaneously, so changes in one cell cannot immediately affect its neighbors.
  • Use an in-place strategy by encoding the transition states within the board.
  • Introduce temporary values to represent state changes: for example, mark a cell that was live but now dead, and a cell that was dead but now live.
  • When counting live neighbors, consider the cell's original state, which can be recovered using the absolute value or a defined mapping.

Space and Time Complexity

Time Complexity: O(m * n) – we check each cell and its at most 8 neighbors. Space Complexity: O(1) – updates are performed in-place without extra auxiliary storage.

Solution

We can solve the problem in-place by using intermediate states:

  • Use -1 to represent a cell that was originally live (1) but becomes dead (0).
  • Use 2 to represent a cell that was originally dead (0) but becomes live (1).

During the first pass, for each cell count the live neighbors (treating a cell as originally live if its value is 1 or -1). Then, update the cell using the Game of Life rules:

  • If a cell is dead (0) and has exactly 3 live neighbors, mark it as 2 (becomes live).
  • If a cell is live (1) and has fewer than 2 or more than 3 live neighbors, mark it as -1 (dies).

In a second pass, finalize the board by converting cells:

  • If the value is > 0 (either 1 or 2), set the cell to 1.
  • Otherwise, set the cell to 0.

This method leverages in-place modifications while correctly computing neighbor counts based on original states.

Code Solutions

# Python solution
class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        # Dimensions of the board
        rows, cols = len(board), len(board[0])
        
        # Helper function to count live neighbors
        def count_live_neighbors(r, c):
            live = 0
            for i in range(r-1, r+2):  # Loop over row neighbors
                for j in range(c-1, c+2):  # Loop over column neighbors
                    if (i == r and j == c) or i < 0 or j < 0 or i >= rows or j >= cols:
                        continue  # Skip the cell itself and out-of-bound indices
                    # If neighbor was originally live (1 or -1)
                    if abs(board[i][j]) == 1:
                        live += 1
            return live
        
        # First pass: update board using intermediate states
        for r in range(rows):
            for c in range(cols):
                live_neighbors = count_live_neighbors(r, c)
                # Rule 1 or Rule 3: live cell dies if fewer than 2 or more than 3 neighbors
                if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    board[r][c] = -1  # Mark as cell that was live but now becomes dead
                # Rule 4: dead cell becomes live if exactly 3 live neighbors
                if board[r][c] == 0 and live_neighbors == 3:
                    board[r][c] = 2  # Mark as cell that was dead but now becomes live
        
        # Second pass: finalize the board by converting intermediate states to final states
        for r in range(rows):
            for c in range(cols):
                # If cell has positive value, set to live; otherwise, set to dead
                board[r][c] = 1 if board[r][c] > 0 else 0
← Back to All Questions