Game Of Life

If any live cell has less than two live neighbors, then it dies. If any live cell has two or three live neighbors, then it lives onto the next generation. If any live cell has more than three live neighbors, then it dies. A dead element with exactly three live neighbors becomes a live element. Your task is to print the next state of this board using these four rules.

The first line of the input contains an integer T denoting the number of test cases. The first line of every test case contains two space-separated integers N and M, denoting the number of rows and columns, respectively. The next N lines of each test case contain M space-separated integers denoting the elements of the board.

The first element(0,0) and the fourth element(1,1) are ‘live’ and have one live and two dead neighbors. Hence they both will die and become 0 in the next state. The second element(0,1) and the third element(1,0) are ‘dead’ and have one dead and two live neighbors. Hence they will also die and become 0 in the next state.

Greedy Approach

1. Start by creating two arrays, “xDirections” and “yDirections,” containing all the neighbors’ possible directions.

“xDirections” = {0, 0, 1, 1 ,1, -1, -1, -1}

“yDirections” = {1, -1, 1, -1, 0, 0, 1, -1}

2. Run a loop(loop variable ‘i’) from 0 till N.

3. Run another loop inside the above loop(loop variable ‘j’) from 0 till M.

Make an integer variable “liveCount” to keep track of the live elements, i.e., elements with the value ‘1’.
Now run a loop(loop variable ‘k’) from 0 till 8 to visit all the neighbors.
- Make a variable “currentX” = i + xDirections[k], which will store the x coordinate of the current neighborhood element. Similarly, make another variable “currentY” = j + yDirections[k],which will store the y coordinate of the current neighborhood element.
- Increment “liveCount” by one only when it satisfies the following two conditions:
  - The current element is a live element, i.e., the current element’s absolute value is ‘1’.
  - “currentX” and “currentY” are within the board, i.e., the current element lies inside the board.
Now, check if the current element satisfies Rule 4, i.e if board[i][j] = 0(dead) and it has exactly three neighbours(“liveCount” = 3). If this condition is true, update board[i][j] = 2. Hence, board[i][j] = 2 will indicate a element that is now live but was dead earlier.
Similarly, check if the current element satisfies Rule 1 and 3, i.e., board[i][j] = 1, the number of live neighbors(“liveCount”) is either less than 2 or greater than 3. If this condition is true then update board[i][j] = -1. Hence, board[i][j] = -1 will indicate a element which is now dead but was live earlier.
We do not need to check if the current element satisfies Rule 2 since it will be automatically taken care of after checking Rule 1 and Rule 3.

4. After exiting all the above loops, we’ll now perform the following operations to get the board’s next state.

5. Run a loop(loop variable ‘i’) from 0 till N.

Run a nested loop inside the above loop(loop variable ‘j’) from 0 till M.
1. If board[i][j] >= 1, update board[i][j] = 1 , which means this element will be live in the next state.
2. Else update board[i][j] = 0, which means that this element will be dead in the next state.

6. Return “board,” the next state of the board.

Time Complexity

O(N * M), where N is the number of rows and M is the number of board columns.

While traversing the board, the outer loop runs N times, and the nested loop runs M times, and inside this loop, we are iterating on all the eight neighbors. Hence, the final time complexity will be O(N * M * 8) = O(N * M)

Space Complexity

O(1)

As we are using constant memory space.

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Input 1 :

Sample Input 2 :

Sample Output 2 :