Problem #289: Game of Life

Intuition & Strategy Breakdown

Simulate board state transition in-place using bit manipulation or temporary state codes (e.g. 2 for live->dead, 3 for dead->live).

Python Solution

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        # 0: Dead -> Dead
        # 1: Live -> Live
        # 2: Live -> Dead
        # 3: Dead -> Live
        
        rows, cols = len(board), len(board[0])
        
        def countNeighbors(r, c):
            nei = 0
            for i in range(r - 1, r + 2):
                for j in range(c - 1, c + 2):
                    if (i == r and j == c) or i < 0 or j < 0 or \
                        i == rows or j == cols:
                        continue
                    if board[i][j] in [1, 2]:
                        nei += 1
            return nei

        for r in range(rows):
            for c in range(cols):
                nei = countNeighbors(r, c)
                if board[r][c] == 1:
                    if nei < 2 or nei > 3:
                        board[r][c] = 2
                else:
                    if nei == 3:
                        board[r][c] = 3
        
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 1:
                    board[r][c] = 1
                elif board[r][c] == 2:
                    board[r][c] = 0
                elif board[r][c] == 3:
                    board[r][c] = 1
                else:
                    board[r][c] = 0

Java Solution

class Solution {
    public void gameOfLife(int[][] board) {
        int rows = board.length, cols = board[0].length;
        int[][] directions = {{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int liveNeighbors = 0;
                for (int[] d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && 
                        (board[nr][nc] == 1 || board[nr][nc] == 2)) {
                        liveNeighbors++;
                    }
                }
                if (board[r][c] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) board[r][c] = 2;
                if (board[r][c] == 0 && liveNeighbors == 3) board[r][c] = 3;
            }
        }

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 2) board[r][c] = 0;
                else if (board[r][c] == 3) board[r][c] = 1;
            }
        }
    }
}