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:
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.
This C solution uses an additional matrix to store the new state of each cell while retaining the current state in the original matrix. For each cell, its live neighbors are counted, and rules are applied to determine its next state. Once every cell's state is determined, the original board is updated. Memory is dynamically allocated for the copy and freed after use.
C++
Java
Python
C#
JavaScript
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.
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.
The C solution uses the board itself to track changes by representing transitional states so the board can be accurately updated in one iteration by determining the final state in a second pass.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Naive Approach with Extra Space | 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. |
| In-Place State Transition Approach | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. |
Coding Challenge #85: The Game of Life • The Coding Train • 701,308 views views
Watch 9 more video solutions →Practice Game of Life with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor