Game Of Life - Leetcode Solution

Game of Life is a popular problem on LeetCode, it's a simulation problem where we need to simulate the evolving state of cells in a grid following certain rules.

Problem Statement:

You are given a 2D board representing the life of a cell. Each cell has a value of either 0 or 1. The 0 represents the dead cell and 1 represents the live cell. The game of life is a cellular automaton where each cell follows the below rules:

• If a live cell has fewer than two live neighbors, it dies.
• If a live cell has more than three live neighbors, it dies.
• If a dead cell has exactly three live neighbors, it comes back to life.
• If a live cell has exactly two or three live neighbors, it continues to live.

Now, we have to implement a function that takes the board as input and returns an updated board.

Solution:

The problem statement mentions that we have to simulate the changes of evolving cells in the given board. To implement the simulation logic, we can follow these steps:

Step 1: Iterate over each cell in the board. Step 2: For each cell, calculate the number of live neighbors. Step 3: Apply the rules of the game of life to that cell. Step 4: Store the updated state of each cell in a separate board. Step 5: After all cells have been updated, copy the updated board to the original board.

Let's implement this solution in Python:

def gameOfLife(board: List[List[int]]) -> None: row, col = len(board), len(board[0]) updated_board = [[0] * col for _ in range(row)]

def count_live_neighbors(i, j):
    count = 0
    for x in range(max(0, i - 1), min(i + 2, row)):
        for y in range(max(0, j - 1), min(j + 2, col)):
            count += board[x][y]
    count -= board[i][j]
    return count

for i in range(row):
    for j in range(col):
        live_neighbors = count_live_neighbors(i, j)
        cell_state = board[i][j]
        if cell_state == 1 and (live_neighbors == 2 or live_neighbors == 3):
            updated_board[i][j] = 1
        elif cell_state == 0 and live_neighbors == 3:
            updated_board[i][j] = 1

for i in range(row):
    for j in range(col):
        board[i][j] = updated_board[i][j]

Let's understand the code step by step:

• In the function signature, we have taken the input board as a List of Lists and the return type as None.
• We have initialized the row and col variable to the dimensions of the input board and created an updated_board with the same size.
• We have defined a nested function called count_live_neighbors which takes the current cell's indices as arguments and returns the count of live neighbors.
• In the main loop, we have iterated over each cell in the board and calculated the number of live neighbors using the count_live_neighbors function.
• We have applied the rules of the game of life to update the current cell, and stored the updated state in the updated_board.
• Finally, we have copied the updated_board to the original board.

Complexity Analysis:

• Time Complexity: O(row * col) because we are iterating over each cell in the board once.
• Space Complexity: O(row * col) because we are creating an updated copy of the board in memory.

Conclusion:

In this blog post, we discussed the Game of Life problem on LeetCode and implemented its solution in Python. We followed a step-by-step approach to simulate the evolution of cells in the input board and update their state using the game of life rules. This problem teaches us the importance of breaking down a complex problem into smaller sub-problems and solving them step by step.

1