[LeetCode/Python] 289. Game of Life

📌 Problem

[LeetCode] 289. Game of Life

📌 Solution

Idea

The main difficulty is that all cells must be updated simultaneously, while we are required to modify the board in-place.

To solve this, we encode both the original state and the next state in a single cell using temporary values.

State Encoding

Value	Meaning
0	dead → dead
1	live → live
2	dead → live (birth)
3	live → dead (death)

Key observation:

• When counting neighbors, we must check whether a cell was originally live
• Cells with value 1 or 3 were originally live

Steps

1. Direction Vector
   Use a fixed list of 8 directions to visit all neighbors.

   dirs = [(-1,-1), (-1,0), (-1,1),
           ( 0,-1),         ( 0,1),
           ( 1,-1), ( 1,0), ( 1,1)]

2. First Pass — Count Neighbors & Encode State
   For each cell (i, j):
   1. Count the number of originally live neighbors
   2. Apply the Game of Life rules
   3. Encode the transition using values 0, 1, 2, 3
3. Second Pass — Finalize Board
   After the first pass, convert encoded values to final states:
   • 1, 2 → 1 (live)
   • 0, 3 → 0 (dead)

Code

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return

        m, n = len(board), len(board[0])

        # 8 directions
        dirs = [(-1, -1), (-1, 0), (-1, 1),
                ( 0, -1),          ( 0, 1),
                ( 1, -1), ( 1, 0), ( 1, 1)]

        def was_live(x: int) -> bool:
            # originally live cells are 1 (live->live) or 3 (live->dead)
            return x == 1 or x == 3
        
        # 1) State encoding 
        #    (0: 0->0, 1: 1->1, 2: 0->1, 3: 1->0)
        for i in range(m):
            for j in range(n):
                live_neighbors = 0
                for di, dj in dirs:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n and was_live(board[ni][nj]):
                        live_neighbors += 1

                if was_live(board[i][j]):  # originally live
                    if live_neighbors < 2 or live_neighbors > 3:
                        board[i][j] = 3  # live -> dead
                    else:
                        board[i][j] = 1  # live -> live
                else:  # originally dead
                    if live_neighbors == 3:
                        board[i][j] = 2  # dead -> live
                    else:
                        board[i][j] = 0  # dead -> dead
        
        # 2) State encoding -> Finalize to 0/1
        for i in range(m):
            for j in range(n):
                board[i][j] = 1 if board[i][j] in (1, 2) else 0

Complexity

• Time Complexity: $O(mn)$
• Space Complexity: $O(1)$ (in-place, constant extra space)

🚀 Key Takeaways

• In-place problems often require state encoding
• Always distinguish original state vs next state
• Two-pass strategy is common for simultaneous updates
• Similar pattern appears in:
  • Game of Life
  • Set Matrix Zeroes
  • Board / grid simulation problems