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):
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.
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] is 0 or 1.Follow up:
The Game of Life problem simulates the evolution of cells on a 2D grid based on a fixed set of rules. Each cell’s next state depends on the number of its eight neighbors that are alive. The key challenge is updating the grid simultaneously without corrupting neighbor information needed for other cells.
A straightforward approach is to create a separate copy of the board, compute the next state for each cell using the original board, and then write results to the copy. This keeps transitions clean but requires additional space.
A more optimized approach performs the update in-place by encoding transitional states (for example using temporary markers). This allows the algorithm to determine both the previous and next state of each cell during traversal. After processing all cells, a final pass converts transitional markers into their final states.
Both approaches iterate through every cell and check its neighbors, leading to O(m × n) time complexity. The optimized in-place simulation reduces extra space usage to O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Copy Grid Simulation | O(m × n) | O(m × n) |
| In-place State Encoding | O(m × n) | O(1) |
The Coding Train
This approach creates a copy of the original board. It calculates the new state for each cell using the current state from the original board while updating the new state in the copy. Once all cells have been processed, it updates the original board with the calculated states from the copy.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, because each cell is visited once.
Space Complexity: O(m * n), due to the additional copy of the board.
1#include <vector>
2using namespace std;
3
4void gameOfLife(vector<vector<int>>& board) {
5 int m = board.size(), n = board[0].size();
6 vector<vector<int>> copy = board;
7 vector<pair<int, int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
8
9 for (int i = 0; i < m; i++) {
10 for (int j = 0; j < n; j++) {
11 int liveNeighbors = 0;
12 for (auto d : directions) {
13 int ni = i + d.first, nj = j + d.second;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] == 1) {
liveNeighbors++;
}
}
if (copy[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[i][j] = 0;
} else if (copy[i][j] == 0 && liveNeighbors == 3) {
board[i][j] = 1;
}
}
}
}
The C++ solution follows a similar approach to the C version, using a temporary board to store the current state. It utilizes STL vectors and iterates over all cells, checking live neighbors from eight possible directions. Once the next state is computed for all cells, the original board is updated.
This approach uses in-place updates by leveraging different state values. We introduce temporary states: 2 represents a cell that was originally live (1) but will be dead in the next state, and -1 represents a cell that was dead (0) but will be live in the next state. At the end, these temporary states are converted to the final states.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no additional space is used beyond input storage.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Game of Life is a common matrix simulation problem that appears in coding interviews at major tech companies. It tests skills in grid traversal, careful state management, and space optimization.
The optimal approach updates the board in-place by encoding transitional states. This allows you to track both the original and future state of each cell while scanning the grid. It avoids allocating another matrix and reduces space complexity to O(1).
Temporary states help preserve the original state of cells while computing the next generation. Without them, updating one cell could affect neighbor calculations for other cells in the same iteration.
A 2D array (matrix) is the most suitable structure because the board represents a grid of cells. It allows easy traversal and neighbor checks in eight directions for each cell.
JavaScript sacrifices individual replication arrangements by relying heavily on synthetic prescript methods without overabstracting variable state calculations, mitigating excessive interplay.