NUHMAN.com

Introduction

LeetCode 289: Game of Life is a problem inspired by the famous Game of Life, a cellular automaton devised by mathematician John Conway. In this problem, you are given a 2D grid representing the game board, where each cell can either be alive (represented by 1) or dead (represented by 0). The game progresses in generations, with each cell evolving based on the following rules:

1. Any live cell with fewer than two live neighbors dies (underpopulation).
2. Any live cell with two or three live neighbors lives on to the next generation (survival).
3. Any live cell with more than three live neighbors dies (overpopulation).
4. Any dead cell with exactly three live neighbors becomes alive (reproduction).

Your task is to update the board to its next state after one generation.

Problem Statement

You are given an m x n matrix board representing the state of the game. Each cell in the matrix has two possible states:

• 1 (alive)
• 0 (dead)

Update the board to its next state after applying the above rules.

The problem is to be solved in-place, meaning you must modify the input matrix directly, using O(1) extra space.

Example

python

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

Output:
[
 [0, 0, 0],
 [1, 0, 1],
 [0, 1, 0]
]

✅ Step-by-Step Solution

🧠 Intuition

The Game of Life operates on a matrix, and you need to apply the rules of evolution to each cell. However, since you are required to update the board in-place, we need to come up with a way to track changes without overwriting values prematurely. This can be accomplished using a clever encoding strategy:

• State Encoding:
• Use two bits per cell: The original state (alive or dead) can be combined with the next state.
• For example, if a cell is alive in the current state, it can be represented as 01 (alive and will stay alive), while a cell that is dead in the current state can be represented as 10 (dead and will become alive).

✅ Approach

Steps:

1. Bitwise Encoding:

• Use the first bit of each cell to store its current state (0 for dead, 1 for alive).
• Use the second bit to store the next state after applying the rules (0 for dead, 2 for alive).

1. Neighbor Counting:

• Iterate through the board and check the 8 neighbors of each cell to count how many are alive.
• Use this count to determine the next state of the cell.

1. Final Update:

• After determining the next state for each cell, decode the final state by masking out the old state, leaving only the new state.

✅ Python Code

python

class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        if not board or not board[0]:
            return
        
        m, n = len(board), len(board[0])
        
        # Directions for the 8 neighbors (top, bottom, left, right, 4 diagonals)
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
        
        # Iterate through each cell
        for i in range(m):
            for j in range(n):
                live_neighbors = 0
                # Check the 8 neighbors
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n and (board[ni][nj] == 1 or board[ni][nj] == 2):
                        live_neighbors += 1
                
                # Apply the Game of Life rules
                if board[i][j] == 1 and (live_neighbors == 2 or live_neighbors == 3):
                    # Cell stays alive
                    board[i][j] = 3  # Mark as alive (1) and will stay alive in next generation
                elif board[i][j] == 0 and live_neighbors == 3:
                    # Cell becomes alive
                    board[i][j] = 2  # Mark as dead (0) but will become alive in next generation

        # Final pass to decode the result
        for i in range(m):
            for j in range(n):
                # Shift the new state to the first bit
                board[i][j] >>= 1

🧪 How It Works

1. Neighbor Counting:

• For each cell in the matrix, we count how many of its 8 neighboring cells are alive (1 or 2 — 2 represents a cell that will be alive in the next generation).

1. Applying Rules:

• If the current cell is alive (1) and has 2 or 3 live neighbors, it remains alive (3 — which means alive in the current and next generation).
• If the current cell is dead (0) and has exactly 3 live neighbors, it becomes alive (2 — which means dead now but will be alive next).

1. Final Update:

• After processing all cells, we shift each cell to the right by 1 bit (>> 1) to extract the final state (alive or dead).

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(m * n), where m is the number of rows and n is the number of columnsSpace ComplexityO(1), since the update is done in-place

• The time complexity is O(m * n) because we need to iterate through all the cells in the matrix to calculate the new state.
• The space complexity is O(1) since no extra space is used apart from the given matrix.

🔍 Edge Cases

1. Empty Board: If the board is empty (i.e., board = [] or a row has no elements), the algorithm should return immediately without doing any work.
2. Board with All Dead Cells: If all cells are dead, the board may remain unchanged after applying the rules.
3. Board with All Alive Cells: If all cells are alive, the board may change according to the rules of the game (e.g., some cells might die due to overpopulation).
4. Small Boards: The algorithm should handle very small boards (e.g., 1x1 or 2x2 grids).

✅ Conclusion

LeetCode 289: Game of Life is a fascinating problem that challenges you to simulate cellular automaton rules while updating the board in-place. The key to solving this problem efficiently is encoding the state transitions using bitwise operations to keep track of the current and next state of each cell.

This solution is optimal in both time and space, ensuring it works well even for large boards.