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.
Examples:
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]]Solution in Python
Python
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# Step 1: Define the dimensions of the board
rows, cols = len(board), len(board[0])
# Step 2: Create a helper function to count live neighbors for each cell
def count_live_neighbors(r, c):
# All 8 possible directions (horizontal, vertical, diagonal)
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
live_neighbors = 0
# Check all the surrounding neighbors
for dr, dc in directions:
nr, nc = r + dr, c + dc
# Ensure the neighbor is within bounds and check if it is currently live
# We use abs(board[nr][nc]) to also account for transitional states
if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:
live_neighbors += 1
return live_neighbors
# Step 3: Iterate through each cell and apply the rules
for r in range(rows):
for c in range(cols):
# Count live neighbors
live_neighbors = count_live_neighbors(r, c)
# Rule 1: Any live cell with fewer than two live neighbors dies (underpopulation)
# Rule 2: Any live cell with two or three live neighbors stays alive
# Rule 3: Any live cell with more than three live neighbors dies (overpopulation)
if board[r][c] == 1:
if live_neighbors < 2 or live_neighbors > 3:
# Mark cell as dead in the next state, but it's currently live (1 -> -1)
board[r][c] = -1
# Rule 4: Any dead cell with exactly three live neighbors becomes a live cell
elif board[r][c] == 0:
if live_neighbors == 3:
# Mark cell as live in the next state, but it's currently dead (0 -> 2)
board[r][c] = 2
# Step 4: Final pass to update the board to the new state
for r in range(rows):
for c in range(cols):
# If the cell was marked as -1, it means it was live and is now dead
if board[r][c] == -1:
board[r][c] = 0
# If the cell was marked as 2, it means it was dead and is now live
elif board[r][c] == 2:
board[r][c] = 1Explanation:
- State Transition Encoding:
- To handle the in-place update, we use intermediate states to avoid conflicts when counting neighbors:
1→-1: The cell is currently live but will die.0→2: The cell is currently dead but will become live.
- To handle the in-place update, we use intermediate states to avoid conflicts when counting neighbors:
- Count Live Neighbors:
- We define a helper function
count_live_neighborsto count how many live neighbors each cell has. This function checks the 8 possible directions around a cell (top-left, top, top-right, left, right, bottom-left, bottom, bottom-right).
- We define a helper function
- Rules Implementation:
- For each cell, we apply the Game of Life rules:
- If the cell is live and has fewer than 2 or more than 3 live neighbors, it dies.
- If the cell is dead and has exactly 3 live neighbors, it becomes live.
- For each cell, we apply the Game of Life rules:
- Final Update:
- After marking all the cells with transitional states (
-1for live-to-dead,2for dead-to-live), we go through the board one more time and finalize the transitions:- Convert
-1to0(dead). - Convert
2to1(live).
- Convert
- After marking all the cells with transitional states (
Solution in C++
C++
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
// Step 1: Get the dimensions of the board
int rows = board.size();
int cols = board[0].size();
// Step 2: Create a helper function to count live neighbors for each cell
auto countLiveNeighbors = [&](int r, int c) -> int {
// All 8 possible directions (horizontal, vertical, diagonal)
vector<pair<int, int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int liveNeighbors = 0;
// Check all surrounding neighbors
for (auto dir : directions) {
int nr = r + dir.first;
int nc = c + dir.second;
// Ensure the neighbor is within bounds and count if it's live
// We use abs(board[nr][nc]) to also account for transitional states
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && abs(board[nr][nc]) == 1) {
liveNeighbors++;
}
}
return liveNeighbors;
};
// Step 3: Iterate through each cell and apply the rules
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
// Count live neighbors
int liveNeighbors = countLiveNeighbors(r, c);
// Rule 1 & 3: Any live cell with fewer than 2 or more than 3 live neighbors dies
if (board[r][c] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
// Mark cell as dead in the next state, but it's currently live (1 -> -1)
board[r][c] = -1;
}
// Rule 4: Any dead cell with exactly 3 live neighbors becomes a live cell
if (board[r][c] == 0 && liveNeighbors == 3) {
// Mark cell as live in the next state, but it's currently dead (0 -> 2)
board[r][c] = 2;
}
}
}
// Step 4: Final pass to update the board to the new state
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
// If the cell was marked as -1, it means it was live and is now dead
if (board[r][c] == -1) {
board[r][c] = 0;
}
// If the cell was marked as 2, it means it was dead and is now live
else if (board[r][c] == 2) {
board[r][c] = 1;
}
}
}
}
};Solution in Javascript
JavaScript
var gameOfLife = function(board) {
// Step 1: Get the dimensions of the board
const rows = board.length;
const cols = board[0].length;
// Step 2: Helper function to count live neighbors for a given cell
const countLiveNeighbors = (r, c) => {
// All 8 possible directions (horizontal, vertical, diagonal)
const directions = [
[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1]
];
let liveNeighbors = 0;
// Check all 8 directions around the cell (r, c)
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
// Make sure the neighboring cell is within bounds
// We use Math.abs(board[nr][nc]) to check if a cell was originally alive (1 or -1)
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && Math.abs(board[nr][nc]) === 1) {
liveNeighbors++;
}
}
return liveNeighbors;
};
// Step 3: Iterate through each cell and apply the rules
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
// Count live neighbors for the current cell
const liveNeighbors = countLiveNeighbors(r, c);
// Rule 1 & 3: Any live cell with fewer than 2 or more than 3 live neighbors dies
if (board[r][c] === 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
// Mark the cell as dead in the next state (live -> dead, 1 -> -1)
board[r][c] = -1;
}
// Rule 4: Any dead cell with exactly 3 live neighbors becomes a live cell
if (board[r][c] === 0 && liveNeighbors === 3) {
// Mark the cell as live in the next state (dead -> live, 0 -> 2)
board[r][c] = 2;
}
}
}
// Step 4: Update the board to the new state
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
// If the cell was marked as -1, it means it was live and is now dead
if (board[r][c] === -1) {
board[r][c] = 0;
}
// If the cell was marked as 2, it means it was dead and is now live
if (board[r][c] === 2) {
board[r][c] = 1;
}
}
}
};Solution in Java
Java
class Solution {
public void gameOfLife(int[][] board) {
// Step 1: Get the dimensions of the board
int rows = board.length;
int cols = board[0].length;
// Step 3: Apply the rules for each cell
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// Count the live neighbors for the current cell
int liveNeighbors = countLiveNeighbors(board, r, c);
// Rule 1 & 3: Any live cell with fewer than 2 or more than 3 live neighbors dies
if (board[r][c] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
// Mark the cell as dead in the next state (live -> dead, 1 -> -1)
board[r][c] = -1;
}
// Rule 4: Any dead cell with exactly 3 live neighbors becomes live
if (board[r][c] == 0 && liveNeighbors == 3) {
// Mark the cell as live in the next state (dead -> live, 0 -> 2)
board[r][c] = 2;
}
}
}
// Step 4: Final pass to update the board to the new state
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// If the cell was marked as -1, it means it was live and is now dead
if (board[r][c] == -1) {
board[r][c] = 0;
}
// If the cell was marked as 2, it means it was dead and is now live
if (board[r][c] == 2) {
board[r][c] = 1;
}
}
}
}
// Step 2: Move the helper function outside the gameOfLife method
// Helper function to count live neighbors for a given cell
private int countLiveNeighbors(int[][] board, int r, int c) {
// All 8 possible directions (horizontal, vertical, diagonal)
int[][] directions = {
{-1, -1}, {-1, 0}, {-1, 1},
{0, -1}, {0, 1},
{1, -1}, {1, 0}, {1, 1}
};
int liveNeighbors = 0;
int rows = board.length;
int cols = board[0].length;
// Check all 8 surrounding neighbors
for (int[] direction : directions) {
int nr = r + direction[0];
int nc = c + direction[1];
// Ensure the neighbor is within bounds
// Use Math.abs(board[nr][nc]) to check if it was originally live (1 or -1)
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && Math.abs(board[nr][nc]) == 1) {
liveNeighbors++;
}
}
return liveNeighbors;
}
}