LeetCode 289: Game of Life Solution in Python – A Step-by-Step Guide

What Is LeetCode 289: Game of Life?

In LeetCode 289: Game of Life, you’re given a 2D board where each cell is either alive (1) or dead (0). You need to update it in-place for the next generation based on these rules: 1. An alive cell with fewer than 2 live neighbors dies (underpopulation). 2. An alive cell with 2 or 3 live neighbors lives on. 3. An alive cell with more than 3 live neighbors dies (overpopulation). 4. A dead cell with exactly 3 live neighbors becomes alive (reproduction).

A neighbor is any of the 8 surrounding cells (up, down, left, right, and diagonals). For example, a board like [[0, 1, 0], [0, 0, 1], [1, 1, 1]] changes based on these rules, and you can’t use a whole new board unless you’re sneaky about it. This problem tests your grid skills, feeling a bit like LeetCode 286: Walls and Gates.

Problem Statement

• Input: A 2D integer array board with 0 (dead) or 1 (alive).
• Output: The array board, updated in-place for the next generation.
• Rules: Follow Conway’s Game of Life rules; update all cells at once; prefer in-place.

Constraints

• Grid size: m x n, where 1 ≤ m, n ≤ 25.
• Values: 0 or 1.

Examples

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

Understanding the Problem: Bringing Cells to Life

To solve LeetCode 289: Game of Life in Python, we need to update every cell in the board based on its 8 neighbors, following the four rules—all at the same time, and ideally without making a new grid. For a cell with 1, we count its live neighbors to see if it stays 1 or turns 0; for a 0, we check if it flips to 1. The “in-place” part is tricky because changing one cell could mess up counts for others. We’ll use:

• Best Solution (In-Place with State Encoding): O(m*n) time, O(1) space—super clever.
• Alternative Solution (Extra Board): O(m*n) time, O(m*n) space—easier but uses more room.

Let’s dive into the in-place solution with a friendly breakdown that’s easy to follow.

Best Solution: In-Place with State Encoding

Why This Is the Best Solution

The in-place state encoding method is the top choice for LeetCode 289 because it runs in O(m*n) time—checking each cell once—and uses O(1) space, meaning no extra grid. It’s tricky but brilliant: we use special numbers to mark what a cell was and will be, so we can count neighbors correctly and update later. It’s like leaving little notes on each cell without needing a second board—perfect for this challenge!

How It Works

Let’s imagine the grid as a little town where cells are people, and we’re updating their status:

• Step 1: Use Secret Codes:
• Normally, cells are 0 (dead) or 1 (alive). We’ll add temporary codes:
• If a cell was 0 and stays 0, keep it 0.
• If a cell was 0 and becomes 1, mark it 2.
• If a cell was 1 and stays 1, keep it 1.
• If a cell was 1 and becomes 0, mark it 3.
• These codes let us see the original state (0 or 1) while planning the next state.

• Step 2: Count Neighbors and Mark Changes:
• Go through each cell in the grid.
• Count its 8 neighbors’ live cells (1 or 3 means originally alive).
• Apply the rules:
• Alive (1): < 2 or > 3 neighbors → 3 (dies); 2 or 3 → 1 (stays).
• Dead (0): 3 neighbors → 2 (lives); else → 0 (stays).
• Write the new code in the cell.

• Step 3: Fix the Codes:
• Go through the grid again.
• Change 2 or 3 back to 1 or 0 by taking the value mod 2 (2 % 2 = 0, 3 % 2 = 1).

• Step 4: Why It Works:
• The codes keep track of old and new states at once.
• When counting, we look at the original state (1 or 3), so updates don’t mess us up.
• The final mod step cleans it up to 0s and 1s, all in the same grid.

It’s like giving each cell a sticky note with its past and future, then peeling it off at the end!

Step-by-Step Example

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

• Initial: [[0, 1, 0], [0, 0, 1]].
• Step 1: Count and Encode:
• (0, 0): 0, neighbors (0, 1, 1) = 1 → stays 0.
• (0, 1): 1, neighbors (0, 0, 0, 1) = 1 → < 2, dies → 3.
• (0, 2): 0, neighbors (1, 1) = 2 → stays 0.
• (1, 0): 0, neighbors (0, 1) = 1 → stays 0.
• (1, 1): 0, neighbors (0, 1, 0, 1) = 2 → stays 0.
• (1, 2): 1, neighbors (0, 1) = 1 → < 2, dies → 3.
• After Encoding: [[0, 3, 0], [0, 0, 3]].
• Step 2: Decode:
• 0 % 2 = 0, 3 % 2 = 1, 0 % 2 = 0, etc.
• Result: [[0, 1, 0], [0, 0, 1]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        if not board or not board[0]:
            return

        m, n = len(board), len(board[0])  # Grid size

        # Step 1: Helper to count live neighbors
        def count_neighbors(row, col):
            count = 0
            # Check all 8 directions
            for dr, dc in [(-1, -1), (-1, 0), (-1, 1), (0, -1), 
                          (0, 1), (1, -1), (1, 0), (1, 1)]:
                r, c = row + dr, col + dc
                if 0 <= r < m and 0 <= c < n:
                    # 1 or 3 means originally alive
                    count += 1 if board[r][c] in [1, 3] else 0
            return count

        # Step 2: Mark changes with codes
        for i in range(m):
            for j in range(n):
                live = count_neighbors(i, j)  # Count live neighbors
                if board[i][j] == 1:  # Alive cell
                    if live < 2 or live > 3:
                        board[i][j] = 3  # Dies
                    # Else stays 1
                elif board[i][j] == 0 and live == 3:  # Dead cell
                    board[i][j] = 2  # Becomes alive

        # Step 3: Update to final states
        for i in range(m):
            for j in range(n):
                board[i][j] %= 2  # 0→0, 1→1, 2→0, 3→1

• Line 4-6: Skip if the board’s empty.
• Line 7: Get rows (m) and columns (n).
• Line 9-17: Helper count_neighbors:
• Check 8 directions around a cell.
• If in bounds, add 1 to count if neighbor is 1 or 3 (was alive).
• Line 19-27: First pass:
• For each cell, count live neighbors.
• Alive (1): < 2 or > 3 → 3 (dies); else stays 1.
• Dead (0): 3 neighbors → 2 (lives); else stays 0.
• Line 29-31: Second pass:
• Mod 2 fixes codes: 0→0, 1→1, 2→0, 3→1.

• Time Complexity: O(m*n)—two passes over the grid.
• Space Complexity: O(1)—no extra space, just the board.

This is like a secret code dance—mark, then reveal!

Alternative Solution: Using an Extra Board

Why an Alternative Approach?

Using an extra board is O(mn) time and O(mn) space—simpler but takes more room. It makes a copy of the board, counts neighbors from the original, and updates the copy, then swaps it back. It’s easier to follow, like drawing a new map before erasing the old one.

How It Works

Imagine sketching a new grid:

• Step 1: Copy the board.
• Step 2: For each cell in the copy, count neighbors in the original, apply rules, and update the copy.
• Step 3: Copy the new grid back to the original.

It’s like working on a draft before making it official!

Step-by-Step Example

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

• Original: [[0, 1], [1, 0]].
• Copy: [[0, 1], [1, 0]].
• Update Copy:
• (0, 0): 0, 2 neighbors → stays 0.
• (0, 1): 1, 1 neighbor → dies → 0.
• (1, 0): 1, 1 neighbor → dies → 0.
• (1, 1): 0, 2 neighbors → stays 0.
• New Copy: [[0, 0], [0, 0]].
• Update Original: [[0, 0], [0, 0]].

Code for Extra Board Approach

Copy codeclass Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        m, n = len(board), len(board[0])
        new_board = [[0] * n for _ in range(m)]  # New grid

        def count_neighbors(r, c):
            count = 0
            for dr, dc in [(-1, -1), (-1, 0), (-1, 1), (0, -1), 
                          (0, 1), (1, -1), (1, 0), (1, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    count += board[nr][nc]
            return count

        for i in range(m):
            for j in range(n):
                live = count_neighbors(i, j)
                if board[i][j] == 1:
                    new_board[i][j] = 1 if 2 <= live <= 3 else 0
                else:
                    new_board[i][j] = 1 if live == 3 else 0

        for i in range(m):
            for j in range(n):
                board[i][j] = new_board[i][j]

• Time Complexity: O(m*n)—one pass.
• Space Complexity: O(m*n)—extra board.

It’s a clear but space-heavy way.

Comparing the Two Solutions

• In-Place (Best):
• Pros: O(m*n) time, O(1) space, clever.
• Cons: Tricky encoding.
• Extra Board (Alternative):
• Pros: O(m*n) time, simple logic.
• Cons: O(m*n) space.

In-place wins for space.

Additional Examples and Edge Cases

• [[1]]: → [[0]].
• [[1, 1]]: → [[0, 0]].
• [[0, 0]]: → [[0, 0]].

Both handle these fine.

Complexity Breakdown

• In-Place: Time O(m*n), Space O(1).
• Extra Board: Time O(m*n), Space O(m*n).

In-place is the champ.

Key Takeaways

• In-Place: Codes save space—smart!
• Extra Board: Copy and update—easy!
• Grids: Rules bring them to life.
• Python Tip: Loops and lists rock—see [Python Basics](/python/basics).

Final Thoughts: Play the Game

LeetCode 289: Game of Life in Python is a lively grid puzzle. The in-place solution is a space-saving gem, while the extra board offers a gentle start. Want more? Try LeetCode 286: Walls and Gates or LeetCode 73: Set Matrix Zeroes. Ready to flip some cells? Head to Solve LeetCode 289 on LeetCode and bring that grid to life today!