289. Game of Life
Problem Description
The "Game of Life" is a fascinating cellular automaton created by mathematician John Horton Conway. In this game, we're presented with a grid of cells, each of which can either be alive (denoted by '1') or dead (indicated by '0'). The game progresses in steps, or generations, with each cell's fate in the next generation determined by its current state and the states of its eight neighboring cells. The challenge is to implement an algorithm that takes an m x n grid representing the current state of a board and produces the next state of the board based on the following rules:
- Any living cell with fewer than two live neighbors dies, as if by underpopulation.
- Any living cell with two or three live neighbors lives on to the next generation.
- Any living cell with more than three live neighbors dies, as if by overpopulation.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The game's rules are applied to every cell in the board simultaneously. This means that when calculating the next state, the original state must remain unchanged until all cells have been considered.
Intuition
The solution requires us to update the board to its next state without using additional space to store an intermediate state, which can be tricky because the update of one cell should not affect the update of another cell.
A clever approach to solving this problem within the constraints is to define intermediate states:
- Let state
2represent a cell that was alive but will die in the next state. - Let state
-1represent a cell that was dead but will become alive in the next state.
This way, we can encode the current and next state of a cell within the same grid. A positive value indicates the cell is currently alive, and its specific integer value indicates whether it will stay alive or die in the next state. Similarly, a negative or zero value indicates the cell is currently dead, and the exact value determines if it will remain dead or come to life.
The algorithm proceeds in two passes over the grid:
-
In the first pass, we calculate the next state for each cell without updating the board to the final state. Instead, we use the intermediate states
2and-1if a cell's state is going to change. We use the variableliveto count the number of living neighbors around each cell considering these transitions. -
In the second pass, we update cells in state
2to0(dead) and cells in state-1to1(alive), thus applying the transitions and achieving the next state of the board.
This approach leverages the fact that the state information is stored in-place with clear rules for interpretation, allowing us to determine a cell's original and next state without additional memory usage.
Solution Approach
The solution is implemented in two major steps: firstly detecting changes that will happen in the next state, and secondly applying these changes to realize the next state. This process happens in-place within the original grid to avoid extra space usage, thanks to the in-place marking strategy explained in the intuition part.
-
The first part of the solution involves iterating over all cells in the grid to determine their fate according to the Game of Life rules. While doing that, we keep track of the cell's state change using temporary markers.
To determine the fate of each cell, we need to count its living neighbors. We create a nested loop to check all neighboring cells. If a neighbor is marked with a positive value, we know it's currently alive. Since we're also interested in cells that are about to change state from living to dead, we slightly modify the neighbor count logic. We start with the count at
-board[i][j], which helps us avoid counting the cell itself if it's alive.We use an
ifcondition with a range to ensure we stay within the bounds of the grid without wrapping around. For each live neighbor, we increment thelivecounter. After counting neighbors, we apply the Game of Life rules:- If a cell is alive (
board[i][j] > 0) but has fewer than two or more than three live neighbors (live < 2orlive > 3), it is marked as2, signifying it will die. - Conversely, a dead cell (indicated by
board[i][j] == 0) with exactly three live neighbors (live == 3) is marked as-1, signifying it will become alive.
- If a cell is alive (
-
Once the first pass is complete, all cells on the board will either have their original values (indicating no change) or will be marked with
2(if they are to die) or-1(if they are to become alive). Therefore, in the second part, we make another pass over the grid to finalize the state transitions.- If a cell is marked
2, this means it was alive but is about to die, so we set it to0. - If a cell is marked
-1, it was dead and is about to come to life, so we set it to1.
- If a cell is marked
By treating the states 2 and -1 as temporary placeholders, the algorithm can keep track of both the current and future states of each cell without needing additional space for storing the grid's state. This efficient handling of the states demonstrates a common strategy in algorithm design called in-place computation, which is particularly useful for saving memory and often necessary when dealing with constraints such as constant space complexities.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a 3x3 grid to illustrate the solution approach:
Current state of the grid: 1 1 1 0 0 0 1 0 1
We will use the rules provided and apply the first phase of the solution. Let's see how we can determine the next state for each cell.
- First Pass (Detection Phase):
- For the cell at position (0, 0), which is alive (1), it has three live neighbors. According to the rules, a living cell with two or three live neighbors lives on. Therefore, this cell does not change.
- For the cell at position (0, 1), which is alive (1), it has three live neighbors. This cell also lives on, so no change.
- For the cell at position (0, 2), which is alive (1), it has two live neighbors. This cell continues to live, resulting in no change.
- The cell at position (1, 0) is dead (0), and it has two live neighbors. It remains dead, as it doesn't meet the reproduction rule (exactly three live neighbors required).
- The cell at position (1, 1) is dead (0) and has four live neighbors. It continues to be dead because it doesn't have exactly three live neighbors to become alive.
- The cell at position (1, 2) is dead (0), with three live neighbors. According to the rules, a dead cell with three live neighbors becomes alive. Therefore, this cell is marked as
-1(an intermediate state showing it will be alive in the next state).
For the corner cells at positions (2, 0) and (2, 2), both being alive with only one living neighbor, they will die due to underpopulation. Thus, these cells are marked as 2.
Intermediate state of the grid after the first pass: 1 1 1 0 -1 0 2 0 2
- Second Pass (Update Phase):
Now we go through the grid again and apply the second part of the algorithm to update the cells.
- Cells at positions (0, 0), (0, 1), (0, 2), and (1, 0) retain the same state since they weren't assigned any intermediate state, staying at
1and0respectively. - The cell at position (1, 1) remains dead, so no change.
- The cell at position (1, 2) was marked as
-1and is set to1to finalize its transition to a live cell. - Cells at positions (2, 0) and (2, 2) were marked as
2(meaning they should die) and are now set to0.
The final state of the grid, representing the next state, is now:
Next state of the grid after the second pass: 1 1 1 0 1 0 0 0 0
This example demonstrates how each cell's next state is determined using intermediate states to facilitate in-place updates, maintaining the integrity of the game's rules without additional space.
Solution Implementation
1class Solution:
2 def gameOfLife(self, board: List[List[int]]) -> None:
3 """
4 Do not return anything, modify 'board' in-place instead.
5 This function computes the next state of the Game of Life board.
6
7 Rules for the Game of Life:
8 1. Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.
9 2. Any live cell with two or three live neighbors lives on to the next generation.
10 3. Any live cell with more than three live neighbors dies, as if by overpopulation.
11 4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
12 """
13
14 # Get the dimensions of the board
15 rows, cols = len(board), len(board[0])
16
17 # Iterate over each cell of the board to compute the next state
18 for row in range(rows):
19 for col in range(cols):
20 live_neighbors = -board[row][col] # Start with the negated cell state to offset the current cell count later
21 # Examine all the neighbor cells in the surrounding 3x3 area
22 for x in range(row - 1, row + 2):
23 for y in range(col - 1, col + 2):
24 # Check if the neighbor is within bounds and is alive
25 if 0 <= x < rows and 0 <= y < cols and board[x][y] > 0:
26 live_neighbors += 1
27 # Apply the rules of the Game of Life for the next state of the cell
28 # If the cell is alive and has too few or too many neighbors, it becomes 'dead' for the next state
29 if board[row][col] and (live_neighbors < 2 or live_neighbors > 3):
30 board[row][col] = 2 # Mark this cell for death
31 # If the cell is dead and has exactly 3 live neighbors, it becomes 'alive' for the next state
32 if board[row][col] == 0 and live_neighbors == 3:
33 board[row][col] = -1 # Mark this cell for life
34
35 # Finalize the next state of the board
36 for row in range(rows):
37 for col in range(cols):
38 # Set the cell state to 'dead' if it was marked for death
39 if board[row][col] == 2:
40 board[row][col] = 0
41 # Set the cell state to 'alive' if it was marked for life
42 elif board[row][col] == -1:
43 board[row][col] = 1
441class Solution {
2 public void gameOfLife(int[][] board) {
3 // numRows and numCols hold the dimensions of the board
4 int numRows = board.length;
5 int numCols = board[0].length;
6
7 // Traverse through every cell of the board
8 for (int row = 0; row < numRows; ++row) {
9 for (int col = 0; col < numCols; ++col) {
10 // Count live neighbors, initializing at -board[row][col] to offset self-counting if alive
11 int liveNeighbors = -board[row][col];
12 for (int i = row - 1; i <= row + 1; ++i) {
13 for (int j = col - 1; j <= col + 1; ++j) {
14 // Check if neighbor is within bounds and alive
15 if (i >= 0 && i < numRows && j >= 0 && j < numCols && board[i][j] > 0) {
16 liveNeighbors++;
17 }
18 }
19 }
20
21 // Apply the Game of Life rules to determine next state:
22
23 // Rule 1 or Rule 3: Any live cell with fewer than two live neighbors
24 // or with more than three live neighbors dies (set to 2 for temporary state)
25 if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
26 board[row][col] = 2;
27 }
28
29 // Rule 4: Any dead cell with exactly three live neighbors becomes a live cell
30 // (set to -1 for temporary state)
31 if (board[row][col] == 0 && liveNeighbors == 3) {
32 board[row][col] = -1;
33 }
34 }
35 }
36
37 // Re-traverse the board to rewrite the temporary states to final states
38 for (int row = 0; row < numRows; ++row) {
39 for (int col = 0; col < numCols; ++col) {
40 // A value of 2 means the cell was previously alive and now is dead
41 if (board[row][col] == 2) {
42 board[row][col] = 0;
43 }
44 // A value of -1 means the cell was previously dead and now is alive
45 else if (board[row][col] == -1) {
46 board[row][col] = 1;
47 }
48 }
49 }
50 }
51}
521class Solution {
2public:
3 // Function that simulates the Game of Life on the given board.
4 void gameOfLife(vector<vector<int>>& board) {
5 int rows = board.size(); // Number of rows in the board
6 int cols = board[0].size(); // Number of columns in the board
7
8 // Iterate over each cell in the board
9 for (int i = 0; i < rows; ++i) {
10 for (int j = 0; j < cols; ++j) {
11 int liveNeighbors = -board[i][j]; // Initialize live neighbors count
12
13 // Iterate over all the neighbors of the current cell
14 for (int x = i - 1; x <= i + 1; ++x) {
15 for (int y = j - 1; y <= j + 1; ++y) {
16 // Check if the neighbor is within the board boundaries and is alive
17 if (x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] > 0) {
18 ++liveNeighbors;
19 }
20 }
21 }
22
23 // Apply the Game of Life rules for living cells
24 if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
25 board[i][j] = 2; // Mark for death
26 }
27 // Apply the Game of Life rules for dead cells
28 if (board[i][j] == 0 && liveNeighbors == 3) {
29 board[i][j] = -1; // Mark for life
30 }
31 }
32 }
33
34 // Update the board with the new state
35 for (int i = 0; i < rows; ++i) {
36 for (int j = 0; j < cols; ++j) {
37 // If the cell was marked for death, make it dead
38 if (board[i][j] == 2) {
39 board[i][j] = 0;
40 } else if (board[i][j] == -1) { // If the cell was marked for life, make it alive
41 board[i][j] = 1;
42 }
43 }
44 }
45 }
46};
471/**
2 * Apply the Game of Life rules to the board in place.
3 * @param board - The 2D array representing the Game of Life board, where 1 is a live cell and 0 is a dead cell.
4 */
5function gameOfLife(board: number[][]): void {
6 const rows = board.length;
7 const cols = board[0].length;
8
9 // Iterate over each cell to apply the Game of Life rules
10 for (let row = 0; row < rows; ++row) {
11 for (let col = 0; col < cols; ++col) {
12 // Initialize live neighbor count; the cell itself is counted and will be subtracted later if alive
13 let liveNeighbors = -board[row][col];
14
15 // Check all 8 neighbors of the current cell
16 for (let x = row - 1; x <= row + 1; ++x) {
17 for (let y = col - 1; y <= col + 1; ++y) {
18 // Check if neighbor coordinates are within the board bounds
19 if (x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] > 0) {
20 // Increment live neighbor count if neighbor is alive
21 ++liveNeighbors;
22 }
23 }
24 }
25
26 // Apply the Game of Life rules:
27 // 1. Any live cell with fewer than two or more than three live neighbors dies
28 if (board[row][col] === 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
29 board[row][col] = 2; // Mark the cell to become dead
30 }
31 // 2. Any dead cell with exactly three live neighbors becomes a live cell
32 if (board[row][col] === 0 && liveNeighbors === 3) {
33 board[row][col] = -1; // Mark the cell to become alive
34 }
35 }
36 }
37
38 // Finalize the board state by changing marked cells to their new states
39 for (let row = 0; row < rows; ++row) {
40 for (let col = 0; col < cols; ++col) {
41 if (board[row][col] === 2) {
42 board[row][col] = 0; // Dead cells become 0
43 }
44 if (board[row][col] === -1) {
45 board[row][col] = 1; // New live cells become 1
46 }
47 }
48 }
49}
50Time and Space Complexity
// The time complexity of the code is O(m * n), where m is the number of rows and n is the number of columns in the board. This is because there are two nested loops that iterate through each cell of the board once.
// The space complexity of the code is O(1) since it modifies the board in place without using any additional space proportional to the size of the input. All changes are made directly on the input board, and only a fixed number of extra variables are used.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
141public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
271function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!