Dare2Solve
The Game of Life is a cellular automaton where each cell in a grid can either be alive (1) or dead (0). The state of each cell in the next iteration is determined by its current state and the states of its eight neighbors. The game evolves based on four simple rules: under-population, over-population, survival, and reproduction.
Initialization:
Start by initializing the board and defining directions for accessing neighbors (horizontal, vertical, and diagonal).
Counting Neighbors:
Write a helper function to count live neighbors for each cell using the defined directions.
Applying Rules:
Traverse each cell in the board.
Use conditional statements to apply the rules of the Game of Life:
For live cells (1):
If it has fewer than two live neighbors or more than three live neighbors, it dies (1 → 0).
If it has two or three live neighbors, it
survives (1 → 1).
For dead cells (0):
0 → 1).Updating the Board: Update the board in place based on the computed next state.
Return: After computing the next state for all cells, return the modified board.
O(m * n), where m is the number of rows and n is the number of columns in the board. We iterate through each cell once to compute the next state.
O(1) excluding the input board, as we modify the board in place without using extra space proportional to the size of the board.
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int rows = board.size();
int cols = board[0].size();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int count = 0;
for (int k = i - 1; k <= i + 1; k++) {
for (int h = j - 1; h <= j + 1; h++) {
if (k >= 0 && k < rows && h >= 0 && h < cols && !(k == i && h == j)) {
if (board[k][h] == 1 || board[k][h] == 2) {
count++;
}
}
}
}
if (board[i][j] == 0 && count == 3) {
board[i][j] = -1;
} else if ((count < 2 || count > 3) && board[i][j] == 1) {
board[i][j] = 2;
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == -1) {
board[i][j] = 1;
} else if (board[i][j] == 2) {
board[i][j] = 0;
}
}
}
}
};
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
rows = len(board)
cols = len(board[0]) if rows > 0 else 0
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
def count_live_neighbors(row, col):
live_count = 0
for dx, dy in directions:
neighbor_row, neighbor_col = row + dx, col + dy
if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols:
if board[neighbor_row][neighbor_col] == 1 or board[neighbor_row][neighbor_col] == 2:
live_count += 1
return live_count
for i in range(rows):
for j in range(cols):
# Count live neighbors
live_neighbors = count_live_neighbors(i, j)
if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
board[i][j] = 2
elif board[i][j] == 0 and live_neighbors == 3:
board[i][j] = -1
for i in range(rows):
for j in range(cols):
if board[i][j] == 2:
board[i][j] = 0 # Convert dead cell (was alive) to 0
elif board[i][j] == -1:
board[i][j] = 1 # Convert live cell (was dead) to 1
class Solution {
public void gameOfLife(int[][] board) {
int rows = board.length;
int cols = board[0].length;
int[] directions = {-1, 0, 1};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int liveNeighbors = 0;
for (int dx : directions) {
for (int dy : directions) {
if (dx == 0 && dy == 0) continue;
int neighborX = i + dx;
int neighborY = j + dy;
if (neighborX >= 0 && neighborX < rows && neighborY >= 0 && neighborY < cols &&
(board[neighborX][neighborY] == 1 || board[neighborX][neighborY] == 2)) {
liveNeighbors++;
}
}
}
if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[i][j] = 2; // 1 -> 0, mark as dead
} else if (board[i][j] == 0 && liveNeighbors == 3) {
board[i][j] = -1; // 0 -> 1, mark as live
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 2) {
board[i][j] = 0;
} else if (board[i][j] == -1) {
board[i][j] = 1;
}
}
}
}
}
var gameOfLife = function (board) {
let row = board.length;
let column = board[0].length;
for (let i = 0; i < row; i++) {
for (let j = 0; j < column; j++) {
let count = 0;
for (let k = i - 1; k <= i + 1; k++) {
for (let h = j - 1; h <= j + 1; h++) {
if (board[k] && board[k][h] !== undefined && !(k === i && h === j)) {
if (board[k][h] > 0) {
count += 1;
}
}
}
}
if (board[i][j] === 0 && count === 3) {
board[i][j] = -1;
} else if ((count < 2 || count > 3) && board[i][j] === 1) {
board[i][j] = 2;
}
}
}
for (let i = 0; i < row; i++) {
for (let j = 0; j < column; j++) {
if (board[i][j] === -1) {
board[i][j] = 1;
} else if (board[i][j] === 2) {
board[i][j] = 0;
}
}
}
};