289. Game of Life
Problem Description
According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.
Example 1:
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]]Example 2:
Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 25board[i][j]is0or1
Follow up:
- Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array. How would you address these problems?
Solution
Python Solution
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
m, n = len(board), len(board[0])
# Helper function to count live neighbors
def countLiveNeighbors(row, col):
count = 0
for i in range(max(0, row-1), min(m, row+2)):
for j in range(max(0, col-1), min(n, col+2)):
if (i != row or j != col) and board[i][j] % 2:
count += 1
return count
# Update board using state encoding:
# 0: dead -> dead = 0
# 1: live -> live = 1
# 2: dead -> live = 0 -> 1
# 3: live -> dead = 1 -> 0
for i in range(m):
for j in range(n):
neighbors = countLiveNeighbors(i, j)
if board[i][j] == 1:
if neighbors < 2 or neighbors > 3:
board[i][j] = 3 # live -> dead
else:
if neighbors == 3:
board[i][j] = 2 # dead -> live
# Update final states
for i in range(m):
for j in range(n):
if board[i][j] == 2:
board[i][j] = 1
elif board[i][j] == 3:
board[i][j] = 0Time Complexity: O(m*n)
Need to traverse the entire board twice.
Space Complexity: O(1)
In-place modification using state encoding.
Java Solution
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
// Helper function to count live neighbors
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int neighbors = countLiveNeighbors(board, i, j, m, n);
if (board[i][j] == 1) {
if (neighbors < 2 || neighbors > 3) {
board[i][j] = 3; // live -> dead
}
} else {
if (neighbors == 3) {
board[i][j] = 2; // dead -> live
}
}
}
}
// Update final states
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 2) {
board[i][j] = 1;
} else if (board[i][j] == 3) {
board[i][j] = 0;
}
}
}
}
private int countLiveNeighbors(int[][] board, int row, int col, int m, int n) {
int count = 0;
for (int i = Math.max(0, row-1); i < Math.min(m, row+2); i++) {
for (int j = Math.max(0, col-1); j < Math.min(n, col+2); j++) {
if ((i != row || j != col) && board[i][j] % 2 == 1) {
count++;
}
}
}
return count;
}
}Time Complexity: O(m*n)
Need to traverse the entire board twice.
Space Complexity: O(1)
In-place modification using state encoding.
C++ Solution
class Solution {
public:
void gameOfLife(vector>& board) {
int m = board.size();
int n = board[0].size();
// Update board using state encoding
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int neighbors = countLiveNeighbors(board, i, j, m, n);
if (board[i][j] == 1) {
if (neighbors < 2 || neighbors > 3) {
board[i][j] = 3; // live -> dead
}
} else {
if (neighbors == 3) {
board[i][j] = 2; // dead -> live
}
}
}
}
// Update final states
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 2) {
board[i][j] = 1;
} else if (board[i][j] == 3) {
board[i][j] = 0;
}
}
}
}
private:
int countLiveNeighbors(vector>& board, int row, int col, int m, int n) {
int count = 0;
for (int i = max(0, row-1); i < min(m, row+2); i++) {
for (int j = max(0, col-1); j < min(n, col+2); j++) {
if ((i != row || j != col) && board[i][j] % 2 == 1) {
count++;
}
}
}
return count;
}
}; Time Complexity: O(m*n)
Need to traverse the entire board twice.
Space Complexity: O(1)
In-place modification using state encoding.
JavaScript Solution
/**
* @param {number[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var gameOfLife = function(board) {
const m = board.length;
const n = board[0].length;
const countLiveNeighbors = (row, col) => {
let count = 0;
for (let i = Math.max(0, row-1); i < Math.min(m, row+2); i++) {
for (let j = Math.max(0, col-1); j < Math.min(n, col+2); j++) {
if ((i !== row || j !== col) && board[i][j] % 2 === 1) {
count++;
}
}
}
return count;
};
// Update board using state encoding
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const neighbors = countLiveNeighbors(i, j);
if (board[i][j] === 1) {
if (neighbors < 2 || neighbors > 3) {
board[i][j] = 3; // live -> dead
}
} else {
if (neighbors === 3) {
board[i][j] = 2; // dead -> live
}
}
}
}
// Update final states
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === 2) {
board[i][j] = 1;
} else if (board[i][j] === 3) {
board[i][j] = 0;
}
}
}
};Time Complexity: O(m*n)
Need to traverse the entire board twice.
Space Complexity: O(1)
In-place modification using state encoding.
C# Solution
public class Solution {
public void GameOfLife(int[][] board) {
int m = board.Length;
int n = board[0].Length;
// Update board using state encoding
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int neighbors = CountLiveNeighbors(board, i, j, m, n);
if (board[i][j] == 1) {
if (neighbors < 2 || neighbors > 3) {
board[i][j] = 3; // live -> dead
}
} else {
if (neighbors == 3) {
board[i][j] = 2; // dead -> live
}
}
}
}
// Update final states
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 2) {
board[i][j] = 1;
} else if (board[i][j] == 3) {
board[i][j] = 0;
}
}
}
}
private int CountLiveNeighbors(int[][] board, int row, int col, int m, int n) {
int count = 0;
for (int i = Math.Max(0, row-1); i < Math.Min(m, row+2); i++) {
for (int j = Math.Max(0, col-1); j < Math.Min(n, col+2); j++) {
if ((i != row || j != col) && board[i][j] % 2 == 1) {
count++;
}
}
}
return count;
}
}Time Complexity: O(m*n)
Need to traverse the entire board twice.
Space Complexity: O(1)
In-place modification using state encoding.
Approach Explanation
The solution uses state encoding to modify the board in-place:
- Key Insight:
- Use additional states to track changes
- Original states: 0 (dead), 1 (live)
- New states: 2 (dead->live), 3 (live->dead)
- Use modulo to check original state
- Algorithm Steps:
- Count live neighbors for each cell
- Apply rules using state encoding
- Convert intermediate states to final states
State encoding explanation:
- 0: Remains dead (0 -> 0)
- 1: Remains alive (1 -> 1)
- 2: Dead to alive (0 -> 1)
- 3: Alive to dead (1 -> 0)
Optimization insights:
- No extra space needed
- Original state preserved during updates
- Efficient neighbor counting
- Handles boundary cases
Edge Cases:
- Single cell board
- All dead cells
- All live cells
- Corner and edge cells