Game of Life Solution In C++/Python/java/JS
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 of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously.
Given the current state of the board, update the board to reflect its next state.
Note that you do not need to return anything.
Examples:
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]]
Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]
Constraints:
- m == board.length
- n == board[i].length
- 1 <= m, n <= 25
- board[i][j] is 0 or 1.
Game of Life Problem
You're given a matrix consisting of 0s and 1s, where each element represents a cell in a board, '0' for a dead cell and '1' for a live cell.
Our job is to update this matrix based on the following rules, which consider all 8 surrounding neighbours of each cell (top, bottom, left, right, and all four diagonals):
- Any cell with a value '1' having fewer than two '1' as its neighbours becomes '0'.
- Any cell with a value '1' having two or three '1' as its neighbours remains '1'.
- Any cell with a value '1' having more than three '1' as its neighbours dies.
- Any cell with a value '0' having exactly three neighbours as '1' becomes a '1'.
Brute Force Approach
Intuition:
Now that we have a clear understanding of the problem, what is the first thought that comes to mind?
Since we don’t want to modify the original board while updating values, we first create a new board of the same size as the given board and initialize it with all zeros. This new board will store the updated state of each cell after applying the rules.
Why do we need a new board?
- If we modify the original board while iterating, we risk affecting calculations for neighbouring cells, leading to incorrect updates.
- Using a new board ensures that we base updates only on the original board's values.
Game of Life Algorithm
We traverse through each cell in the given board. Each cell will be checked to determine whether it remains the same or changes in the next generation.
For each cell (i, j), we will examine its 8 adjacent cells (top, bottom, left, right, and the four diagonals). While doing this, we will count the number of '1's and '0's in these neighbouring cells.
Since the update rules are based on the count of live (1) and dead (0) cells, maintaining these counts will help us determine the new value of (i, j) in the updated board. This ensures that the transition follows the given rules accurately.
How will we examine all 8 neighbours of the cell?
To examine all 8 neighbours of a cell, one straightforward way would be to write 8 separate if conditions, each checking one neighbour and updating the counts of '1's and '0's accordingly.
However, this approach can be verbose and repetitive. Instead, we can do it more elegantly using two nested loops. Here's how:
When we're at a cell (i, j), the relevant neighbouring rows are (i-1, i, i+1), and for each of those, the columns are (j-1, j, j+1).
So, by looping through x from i-1 to i+1 and y from j-1 to j+1, we can cover all 9 positions, including the current cell itself.
Here's what we get from this approach:
(i-1, j-1) (i-1, j) (i-1, j+1)
(i, j-1) (i, j) (i, j+1)
(i+1, j-1) (i+1, j) (i+1, j+1)
Out of these, we ignore (i, j), as that's the current cell we're updating and not one of its neighbours.
This technique is cleaner, easier to manage, and scales well. Additionally, we need to make sure we check bounds so we don't access indices outside the matrix.
This approach helps us efficiently collect neighbour information and apply the update rules correctly.
Once we are done with the count of ones and zeroes from the adjacent neighbours of the current cell we are processing. We then make decisions based on the value of the current cell being '1' or '0'.
If the value of the current cell is '1', we need to determine whether it remains alive or becomes dead in the updated board. According to the rules:
- If the number of neighbouring '1's is less than 2 (underpopulation) or greater than 3 (overpopulation), the cell dies, so we set its value to '0' in the updated board.
- Otherwise, the cell survives, and we set its value to '1'.
On the other hand, if the current cell's value is '0', we check whether it becomes alive:
- If the number of neighbouring '1's is exactly 3, the cell comes to life, so we assign '1' to the updated board.
- If not, the cell remains dead, and we assign '0' to the updated board.
In the end, once we’ve finished processing all the cells and updating their values according to the rules, we will have the complete updated board ready.
At this point, we simply assign the updated board to the original board, replacing it with the new values that represent the next state of the game.
Let us understand this with a video,
Game of Life-Brute Force Approach-Animation
Game of Life Example
Input: board = [[0,1,0], [0,1,0], [0,1,0]]
Output: board = [[0,0,0], [1,1,1], [0,0,0]]
Step-by-Step Execution:
We initialize:
- m = 3, n = 3
- updatedBoard = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Now iterate cell-by-cell.
Cell (0, 0):
Neighbors: (0,1), (1,0), (1,1)
Values at neighbors: 1, 0, 1 → ones = 2, zeroes = 1
Since board[0][0] = 0 and ones ≠ 3 → stays 0
updatedBoard[0][0] = 0
Cell (0, 1):
Neighbors: (0,0), (0,2), (1,0), (1,1), (1,2)
Values at neighbors: 0, 0, 0, 1, 0 → ones = 1, zeroes = 4
Since board[0][1] = 1 and ones < 2 → dies
updatedBoard[0][1] = 0
Cell (0, 2):
Neighbors: (0,1), (1,1), (1,2)
Values at neighbors: 1, 1, 0 → ones = 2, zeroes = 1
Since board[0][2] = 0 and ones ≠ 3 → stays 0
updatedBoard[0][2] = 0
Cell (1, 0):
Neighbors: (0,0), (0,1), (1,1), (2,0), (2,1)
Values at neighbors: 0, 1, 1, 0, 1 → ones = 3, zeroes = 2
Since board[1][0] = 0 and ones == 3 → becomes alive
updatedBoard[1][0] = 1
Cell (1, 1):
Neighbors: all 8 neighbors
Values at neighbors: 0,1,0,0,0,0,1,0 → ones = 2, zeroes = 2
Since board[1][1] = 1 and ones == 2 → stays alive
updatedBoard[1][1] = 1
Cell (1, 2):
Neighbors: (0,1), (0,2), (1,1), (2,1), (2,2)
Values at neighbors: 1, 0, 1, 1, 0 → ones = 3, zeroes = 2
Since board[1][2] = 0 and ones == 3 → becomes alive
updatedBoard[1][2] = 1
Cell (2, 0):
Neighbors: (1,0), (1,1), (2,1)
Values at neighbors: 0, 1, 1 → ones = 2, zeros = 1
Since board[2][0] = 0 and ones ≠ 3 → stays dead
updatedBoard[2][0] = 0
Cell (2, 1):
Neighbors: (1,0), (1,1), (1,2), (2,0), (2,2)
Values at neighbors: 0, 1, 0, 0, 0 → ones = 1, zeroes = 4
Since board[2][1] = 1 and ones < 2 → dies
updatedBoard[2][1] = 0
Cell (2, 2):
Neighbors: (1,1), (1,2), (2,1)
Values at neighbors: 1, 0, 1 → ones = 2, zeroes = 1
Since board[2][2] = 0 and ones ≠ 3 → stays dead
updatedBoard[2][2] = 0
Final updatedBoard:
[
[0, 0, 0],
[1, 1, 1],
[0, 0, 0]
]
Game of Life Algorithm
Step 1: Initialize the Board Dimensions
Determine the number of rows and columns in the given board. This will help to navigate through each cell.
Step 2: Create a New Board for the Updated Values
Before modifying the original board, create a new board of the same size. This board will temporarily store the updated values after applying the rules.
Step 3: Traverse Each Cell in the Original Board
Use two nested loops to go through every cell in the original board. For each cell, you will compute the number of live and dead neighbors.
Step 4: Initialize Counters for Live and Dead Neighbors
For every cell you visit, start by initializing two counters — one to count live neighbors and another to count dead ones.
Step 5: Explore All Eight Neighbors of the Current Cell
Use a nested loop to look at all surrounding positions. These include the top, bottom, left, right, and the four diagonals. Make sure to skip the current cell itself and stay within the board boundaries.
Step 6: Count the Number of Live and Dead Neighbors
While checking each neighbor, increment the live counter if the neighbor is alive, or the dead counter if it is dead.
Step 7: Apply the Game of Life Rules to Determine the New Value
Based on the current cell's value and the number of live neighbors:
- If the cell is alive and has fewer than 2 or more than 3 live neighbors, it becomes dead.
- If the cell is alive and has 2 or 3 live neighbors, it remains alive.
- If the cell is dead and has exactly 3 live neighbors, it becomes alive.
- In all other cases, the cell remains dead.
Step 8: Store the Updated Value in the New Board
Assign the result of the above condition to the corresponding position in the new board.
Step 9: Replace the Original Board with the Updated Board
Once all cells are processed and the new board has the correct values, copy the updated board back into the original board to reflect the new state.
Game of Life Solutions in all languages.
Game of Life Solution in C++.
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
// Get the number of rows and columns
int m = board.size();
int n = board[0].size();
// Create a temporary board for updated values
vector<vector<int>> updatedBoard(m, vector<int>(n));
// Traverse each cell
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// Count live neighbors
int ones = 0;
// Check 8 neighbors
for (int x = i - 1; x <= i + 1; ++x) {
for (int y = j - 1; y <= j + 1; ++y) {
// Skip current cell
if (x == i && y == j) continue;
// Count if inside bounds and cell is alive
if (x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 1) {
ones++;
}
}
}
// Apply rules for live cell
if (board[i][j] == 1) {
if (ones < 2 || ones > 3) updatedBoard[i][j] = 0;
else updatedBoard[i][j] = 1;
}
// Apply rules for dead cell
else {
updatedBoard[i][j] = (ones == 3) ? 1 : 0;
}
}
}
// Copy back updated values to original board
board = updatedBoard;
}
};Game of Life Solution in Java
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
// Make a deep copy of the original board to preserve original values
int[][] copy = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
copy[i][j] = board[i][j];
// Iterate through each cell to apply Game of Life rules
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Count live neighbors
int ones = 0;
for (int x = i - 1; x <= i + 1; x++) {
for (int y = j - 1; y <= j + 1; y++) {
if (x == i && y == j) continue;
if (x >= 0 && x < m && y >= 0 && y < n && copy[x][y] == 1)
ones++;
}
}
// Apply rules to determine new state
if (copy[i][j] == 1) {
if (ones < 2 || ones > 3)
board[i][j] = 0; // Dies
} else {
if (ones == 3)
board[i][j] = 1; // Becomes alive
}
}
}
}
}Game of Life Solution in Python
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
m, n = len(board), len(board[0])
# Make a deep copy to preserve original values during update
copy = [row[:] for row in board]
# Traverse each cell
for i in range(m):
for j in range(n):
# Count live neighbors
ones = 0
for x in range(i - 1, i + 2):
for y in range(j - 1, j + 2):
if x == i and y == j:
continue
if 0 <= x < m and 0 <= y < n and copy[x][y] == 1:
ones += 1
# Apply rules to determine the cell's new state
if copy[i][j] == 1:
if ones < 2 or ones > 3:
board[i][j] = 0
else:
if ones == 3:
board[i][j] = 1Game of Life Solution in Javascript
/**
* @param {number[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var gameOfLife = function(board) {
const m = board.length, n = board[0].length;
// Create a copy of original board
const copy = board.map(row => [...row]);
// Traverse each cell
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// Count live neighbors
let ones = 0;
for (let x = i - 1; x <= i + 1; x++) {
for (let y = j - 1; y <= j + 1; y++) {
if (x === i && y === j) continue;
if (x >= 0 && x < m && y >= 0 && y < n && copy[x][y] === 1)
ones++;
}
}
// Apply game rules
if (copy[i][j] === 1) {
if (ones < 2 || ones > 3)
board[i][j] = 0;
} else {
if (ones === 3)
board[i][j] = 1;
}
}
}
};
Game of Life Complexity Analysis
Time Complexity: O(m x n)
Looping Over Each Cell
- The board contains m rows and n columns.
We visit each cell exactly once, so the total number of iterations across the board is O(m × n).
Processing 8 Neighbors for Each Cell
- For every cell we visit, we examine its 8 neighboring cells.
This check is constant — exactly 8 possible directions (or fewer at edges/corners, but still bounded by 8). - Thus, for each cell, this neighbor-checking step is O(1).
- So, for all m × n cells, this neighbor-checking process takes O(m × n) time overall.
Storing the Results in a New Board
- We use a separate board of the same size to store the updated values.
Writing to this board also takes O(m × n) time, since we update each cell once.
Final Time Complexity:
All operations (traversing, neighbor checking, writing to a new board) are done once per cell.
So the total time complexity is: O(m × n)
Space Complexity: O(m x n)
Definition:
- Auxiliary Space: The extra space or temporary space used by the algorithm excluding the input.
- Total Space Complexity: The overall space used by the algorithm, which includes both the input and any additional space.
Auxiliary Space Complexity
We create an additional board (the updated board) of the same size as the input board to store the new state after applying the rules. This board takes up space proportional to the number of cells.
So, the auxiliary space used is: O(m × n)
No other significant extra data structures (like stacks, queues, hashmaps, etc.) are used — just some integer counters (like ones, zeros) and loop variables, which take O(1) space.
Total Space Complexity
The total space includes:
- The input board: already given, so it’s not counted as additional space.
- The auxiliary space (the updated board): O(m × n)
Thus, the total space complexity is: O(m × n)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.