algoadvance

The problem “Game of Life” is a 2D grid problem where each cell in the grid can be either alive (represented by 1) or dead (represented by 0). The board’s state evolves in iterations based on the following rules:

  1. Any live cell with fewer than two live neighbors dies (underpopulation).
  2. Any live cell with two or three live neighbors lives on (next generation).
  3. Any live cell with more than three live neighbors dies (overpopulation).
  4. Any dead cell with exactly three live neighbors becomes a live cell (reproduction).

Write a function to compute the next state (after one iteration) of the board given its current state.

Clarifying Questions

  1. Does the board change in-place, or can we use extra space?
    • The function should ideally work in-place, but using a small constant amount of extra space is allowed.
  2. What are the typical dimensions of the board?
    • Assume the dimensions m x n of the board are such that the board fits in memory.
  3. What are the edge cases?
    • Consider edge cases like the smallest possible board size (1x1) and boards where all cells are initially live or dead.

Strategy

To modify the board in-place while still retaining information about the original state, we can use marking:

After marking the cells accordingly in the first pass, we can then update the board in the second pass to reflect the marked states.

Code

Here’s a solution utilizing the marking strategy:

```python def gameOfLife(board): def count_live_neighbors(board, i, j): directions = [ (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1) ] live_neighbors = 0 for dr, dc in directions: ni, nj = i + dr, j + dc if 0 <= ni < len(board) and 0 <= nj < len(board[0]) and abs(board[ni][nj]) == 1: live_neighbors += 1 return live_neighbors

rows, cols = len(board), len(board[0])

for i in range(rows):
    for j in range(cols):
        live_neighbors = count_live_neighbors(board, i, j)
        
        if board[i][j] == 1:
            if live_neighbors < 2 or live_neighbors > 3:
                board[i][j] = 2  # Live to Dead
        else:
            if live_neighbors == 3:
                board[i][j] = 3  # Dead to Live

for i in range(rows):
    for j in range(cols):
        if board[i][j] == 2:
            board[i][j] = 0  # Update to Dead
        elif board[i][j] == 3:
            board[i][j] = 1  # Update to Live

Time Complexity

The time complexity of this solution is (O(m \times n)), where (m) is the number of rows and (n) is the number of columns. This results from the need to visit each cell in the grid a fixed number of times (specifically, twice).

The space complexity is (O(1)) because the manipulation is done in-place with only a fixed amount of extra storage for state transitions and neighbor counting.

Try our interview co-pilot at AlgoAdvance.com