Problem Explanation:

Game of Life is cellular automaton devised by the British mathematician John Horton Conway, where each cells will either live or die for the next generation as per their neighbour cells. The game is in an infinite board but here we work on a finite board in a 2D array. Each cell has a initial state of live (1) or dead(0), and they interact with their 8 neighbours (horizontal, vertical, diagonal) using the four rules:

1. Any live cell with fewer than two live neighbors dies due to under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies due to over-population.
4. Any dead cell with exactly three live neighbors becomes a live cell as if by reproduction.

The task is to write a program that computes the next state (after one update) of the board given its current state. The next state will be created by applying above rules simultaneously to every cell in the current state. The board needs to be updated at the same time and one cannot update individual cell first and then use its updated values to update other cells.

Example:

Let's consider a running example to better understand the problem

Given a board (input):

1
2
3[ 0, 1, 0]
4[ 0, 0, 1]
5[ 1, 1, 1]
6[ 0, 0, 0]

The updated board (output) would look like:

1
2
3[ 0, 0, 0]
4[ 1, 0, 1]
5[ 0, 1, 1]
6[ 0, 1, 0]

Solution Approach:

The solution is based on the simulation approach. It follows the below steps:

1. Loop over each cell in the board
2. Check the neighboring cells for each cell, calculate the number of live neighbors.
3. Apply the 4 rules and update the state of the cell (in-place) while making sure that the updated state does not affect the computation of other cells.

We have used the bitwise operation to achieve this. An important point to note here is that we would only use two bits instead of the whole integer. The least significant bit is used for the current state and the second least significant bit for the future state. After we applied the rules for each cell, we would right shift each cell to replace the current state by the next state.

With the aforementioned approach, let's move on to the solutions in various programming languages.

Python Solution:

1
2python
3class Solution:
4    def gameOfLife(self, board) :
5        if not board:
6            return board
7        m = len(board)
8        n = len(board[0])
9        
10        # Directions Array for easy lookup to visit neighbor cells
11        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]
12        
13        # Iterating through each cell of the board.
14        for i in range(m):
15            for j in range(n):
16                live = 0 # To store number of live neighbor cells
17                for d in dirs:
18                    if i + d[0] < 0 or i + d[0] >= m or j + d[1] < 0 or j + d[1] >= n:
19                        continue
20                    if board[i + d[0]][j + d[1]] == 1 or board[i + d[0]][j + d[1]] == -1:
21                        live += 1
22                # Applying the rules:
23                if board[i][j] == 1 and live < 2:
24                    board[i][j] = -1 # was alive in this generation, but will die in next generation.
25                if board[i][j] == 1 and live > 3:
26                    board[i][j] = -1
27                if board[i][j] == 0 and live == 3:
28                    board[i][j] = 2 # was dead in this generation, but will be alive in next generation.
29        
30        # Finally updating the cell states
31        for i in range(m):
32            for j in range(n):
33                if board[i][j] == -1:
34                    board[i][j] = 0
35                if board[i][j] == 2:
36                    board[i][j] = 1

JavaScript Solution:

Here is the equivalent solution in JavaScript

1
2javascript
3function gameOfLife(board) {
4    if (!board) return board;
5    let m = board.length;
6    let n = board[0].length;
7    
8    // Directions Array for easy lookup to visit neighbor cells
9    let dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]];
10    
11    // Iterating through each cell of the board.
12    for (let i=0; i < m; i++){
13        for (let j=0; j < n; j++){
14            let live = 0; // To store number of live neighbor cells
15            for (let d of dirs) {
16                if (i + d[0] < 0 || i + d[0] >= m || j + d[1] < 0 || j + d[1] >= n){
17                    continue;
18                }
19                if (board[i + d[0]][j + d[1]] === 1 || board[i + d[0]][j + d[1]] === -1){
20                    live += 1;
21                }
22                // Applying the rules:
23                if (board[i][j] === 1 && live < 2){
24                    board[i][j] = -1; // was alive in this generation, but will die in next generation.
25                }
26                if (board[i][j] === 1 && live > 3){
27                    board[i][j] = -1;
28                }
29                if (board[i][j] === 0 && live === 3){
30                    board[i][j] = 2; // was dead in this generation, but will be alive in next generation.
31                }
32            }
33        }
34    }
35    // Finally updating the cell states
36    for (let i=0; i<m; i++){
37        for (let j=0; j<n; j++){
38            if (board[i][j] === -1){
39                board[i][j] = 0;
40            }
41            if (board[i][j] === 2){
42                board[i][j] = 1;
43            }
44        }
45    }
46}

Java Solution:

The Java solution follows a similar approach, with the changes around array declaration and for-loop structure.

1
2java
3class Solution {
4    public void gameOfLife(int[][] board) {
5        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
6        int m = board.length;
7        int n = board[0].length;
8
9        for (int i = 0; i < m; i++) {
10            for (int j = 0; j < n; j++) {
11                int live = 0;
12                for (int[] d : dirs) {
13                    if (i + d[0] < 0 || i + d[0] >= m || j + d[1] < 0 || j + d[1] >= n) {
14                        continue;
15                    }
16                    if (board[i + d[0]][j + d[1]] == 1 || board[i + d[0]][j + d[1]] == -1) {
17                        live += 1;
18                    }
19                }
20                if (board[i][j] == 1 && (live < 2 || live > 3)) {
21                    board[i][j] = -1;
22                }
23                if (board[i][j] == 0 && live == 3) {
24                    board[i][j] = 2;
25                }
26            }
27        }
28        for (int i = 0; i < m; i++) {
29            for (int j = 0; j < n; j++) {
30                if (board[i][j] == -1) {
31                    board[i][j] = 0;
32                }
33                if (board[i][j] == 2) {
34                    board[i][j] = 1;
35                }
36            }
37        }
38    }
39}

Each solution reflects the same logic but in the syntax of the respective programming language. They all follow the rules of Game of Life and execute step-by-step through each cell of the board checking the state of neighbours and deciding on the next state. Thus, the next generation of cells is created using cellular automaton.