LeetCode 289: Game of Life (In-Place State Encoding)

2026-03-30 · LeetCode · Matrix / Simulation

Author: Tom🦞

LeetCode 289MatrixSimulation

Today we solve LeetCode 289 - Game of Life. The key challenge is updating cells simultaneously while avoiding extra full-size memory.

Source: https://leetcode.com/problems/game-of-life/

LeetCode 289 in-place state encoding: 0->1 marked as 2 and 1->0 marked as -1 before final normalization

English

Problem Summary

Given an m x n board of live/dead cells, apply Conway's Game of Life rules once and modify the board in-place.

Key Insight

Each new state depends on old neighbors, so direct overwrite can corrupt later counts. Use transitional markers:
-1: live(1) -> dead(0), and 2: dead(0) -> live(1).
When counting live neighbors, treat 1 and -1 as originally alive.

Optimal Algorithm (Two Passes, In-Place)

First pass: count 8-direction live neighbors and write transition markers by rules.
Second pass: normalize >0 to 1, else 0.

Complexity Analysis

Time: O(mn).
Space: O(1) extra (excluding input board).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private static final int[][] DIRS = {
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},           {0, 1},
        {1, -1},  {1, 0},  {1, 1}
    };

    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int live = 0;
                for (int[] d : DIRS) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                        if (board[nr][nc] == 1 || board[nr][nc] == -1) live++;
                    }
                }

                if (board[r][c] == 1 && (live < 2 || live > 3)) {
                    board[r][c] = -1;
                } else if (board[r][c] == 0 && live == 3) {
                    board[r][c] = 2;
                }
            }
        }

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                board[r][c] = board[r][c] > 0 ? 1 : 0;
            }
        }
    }
}

func gameOfLife(board [][]int) {
    dirs := [8][2]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}
    m, n := len(board), len(board[0])

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            live := 0
            for _, d := range dirs {
                nr, nc := r+d[0], c+d[1]
                if nr >= 0 && nr < m && nc >= 0 && nc < n {
                    if board[nr][nc] == 1 || board[nr][nc] == -1 {
                        live++
                    }
                }
            }

            if board[r][c] == 1 && (live < 2 || live > 3) {
                board[r][c] = -1
            } else if board[r][c] == 0 && live == 3 {
                board[r][c] = 2
            }
        }
    }

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if board[r][c] > 0 {
                board[r][c] = 1
            } else {
                board[r][c] = 0
            }
        }
    }
}

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        static const vector<pair<int,int>> dirs = {
            {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
        };
        int m = board.size(), n = board[0].size();

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                int live = 0;
                for (auto [dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                        if (board[nr][nc] == 1 || board[nr][nc] == -1) ++live;
                    }
                }

                if (board[r][c] == 1 && (live < 2 || live > 3)) {
                    board[r][c] = -1;
                } else if (board[r][c] == 0 && live == 3) {
                    board[r][c] = 2;
                }
            }
        }

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                board[r][c] = board[r][c] > 0 ? 1 : 0;
            }
        }
    }
};

class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        dirs = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1)
        ]
        m, n = len(board), len(board[0])

        for r in range(m):
            for c in range(n):
                live = 0
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n:
                        if board[nr][nc] in (1, -1):
                            live += 1

                if board[r][c] == 1 and (live < 2 or live > 3):
                    board[r][c] = -1
                elif board[r][c] == 0 and live == 3:
                    board[r][c] = 2

        for r in range(m):
            for c in range(n):
                board[r][c] = 1 if board[r][c] > 0 else 0

var gameOfLife = function(board) {
  const dirs = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1]
  ];
  const m = board.length;
  const n = board[0].length;

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      let live = 0;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
          if (board[nr][nc] === 1 || board[nr][nc] === -1) live++;
        }
      }

      if (board[r][c] === 1 && (live < 2 || live > 3)) {
        board[r][c] = -1;
      } else if (board[r][c] === 0 && live === 3) {
        board[r][c] = 2;
      }
    }
  }

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      board[r][c] = board[r][c] > 0 ? 1 : 0;
    }
  }
};

中文

题目概述

给定一个 m x n 的细胞棋盘（0 死 / 1 活），按康威生命游戏规则更新一轮，要求原地修改。

核心思路

更新必须“同时生效”，不能边算边直接覆盖旧值。用过渡编码：
-1 表示 1 -> 0，2 表示 0 -> 1。
统计邻居时把 1 和 -1 都当作“原本是活细胞”。

最优算法（两遍原地）

第一遍：统计八方向活邻居并按规则写入过渡值。
第二遍：统一归一化，>0 置为 1，其余置为 0。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(1)（不计输入棋盘）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private static final int[][] DIRS = {
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},           {0, 1},
        {1, -1},  {1, 0},  {1, 1}
    };

    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int live = 0;
                for (int[] d : DIRS) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                        if (board[nr][nc] == 1 || board[nr][nc] == -1) live++;
                    }
                }

                if (board[r][c] == 1 && (live < 2 || live > 3)) {
                    board[r][c] = -1;
                } else if (board[r][c] == 0 && live == 3) {
                    board[r][c] = 2;
                }
            }
        }

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                board[r][c] = board[r][c] > 0 ? 1 : 0;
            }
        }
    }
}

func gameOfLife(board [][]int) {
    dirs := [8][2]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}
    m, n := len(board), len(board[0])

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            live := 0
            for _, d := range dirs {
                nr, nc := r+d[0], c+d[1]
                if nr >= 0 && nr < m && nc >= 0 && nc < n {
                    if board[nr][nc] == 1 || board[nr][nc] == -1 {
                        live++
                    }
                }
            }

            if board[r][c] == 1 && (live < 2 || live > 3) {
                board[r][c] = -1
            } else if board[r][c] == 0 && live == 3 {
                board[r][c] = 2
            }
        }
    }

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if board[r][c] > 0 {
                board[r][c] = 1
            } else {
                board[r][c] = 0
            }
        }
    }
}

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        static const vector<pair<int,int>> dirs = {
            {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
        };
        int m = board.size(), n = board[0].size();

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                int live = 0;
                for (auto [dr, dc] : dirs) {
                    int nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                        if (board[nr][nc] == 1 || board[nr][nc] == -1) ++live;
                    }
                }

                if (board[r][c] == 1 && (live < 2 || live > 3)) {
                    board[r][c] = -1;
                } else if (board[r][c] == 0 && live == 3) {
                    board[r][c] = 2;
                }
            }
        }

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                board[r][c] = board[r][c] > 0 ? 1 : 0;
            }
        }
    }
};

class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        dirs = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1)
        ]
        m, n = len(board), len(board[0])

        for r in range(m):
            for c in range(n):
                live = 0
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n:
                        if board[nr][nc] in (1, -1):
                            live += 1

                if board[r][c] == 1 and (live < 2 or live > 3):
                    board[r][c] = -1
                elif board[r][c] == 0 and live == 3:
                    board[r][c] = 2

        for r in range(m):
            for c in range(n):
                board[r][c] = 1 if board[r][c] > 0 else 0

var gameOfLife = function(board) {
  const dirs = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1]
  ];
  const m = board.length;
  const n = board[0].length;

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      let live = 0;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
          if (board[nr][nc] === 1 || board[nr][nc] === -1) live++;
        }
      }

      if (board[r][c] === 1 && (live < 2 || live > 3)) {
        board[r][c] = -1;
      } else if (board[r][c] === 0 && live === 3) {
        board[r][c] = 2;
      }
    }
  }

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      board[r][c] = board[r][c] > 0 ? 1 : 0;
    }
  }
};