Game Of Life 🪦💐| Daily LeetCode Challenge | Day 12 | Coding Interview

This question has been marked as medium level on leetcode which in reality should be easy. The reason is that the best complexity you can achieve is O(m*n) where m is the number of rows and n is the number of columns and the simplest brute force is giving exactly that (The solution was faster than 100% of other submissions!).

30 Days Interview Preparation Plan: 200+ best coding questions and Behavioural interviews

Let’s start with the description.

We are given a 2D array where each cell has either a 1 or 0 value, These value represents whether life is alive in the cell or dead, 1 is alive and 0 is dead. There are 8 neighbors to each cell unless it's on the border.

There are some rules to this system/game:

1. Any cell dies if the total number of live neighbors is less than 2.
2. Any cell survives to the next level if the total number of neighbors is 2 or 3.
3. A cell dies of overpopulation if the number of neighbors is more than 3.
4. A cell comes to life if the number of alive neighbors is exactly 3.

Game of life

The solution

We know we have to somehow visit every cell at least once to get an idea of its neighborhood, to know the number of alive neighbors.

The algorithm or strategy for this problem

1. Visit every cell using two for loops, the outer loop traverses the row and the inner loop does the column.
2. for each cell, count the number of live neighbors.
3. Based on the given rules above, make necessary changes.

Code in cpp

The code is explained below.