Game of Life

The task is to simulate the “Game of Life” as defined by John Conway. The next state of each cell in the grid is determined by applying specific rules based on the current state and the states of its eight neighbors.

Approach

  1. Iterate through Each Cell: Loop through each cell of the board to determine its next state.
  2. Count Live Neighbors: For each cell, count the number of live neighbors (1s) it has.
  3. Apply Rules: Based on the count of live neighbors and the cell’s current state, apply the rules to determine the next state.
  4. Update In-Place: To update the board in-place without using extra space, you can use temporary states to represent the transition between states.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        m, n = len(board), len(board[0])
        directions = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (1,-1), (-1,1), (-1,-1)]

        for i in range(m):
            for j in range(n):
                live_neighbors = 0
                for d in directions:
                    ni, nj = i + d[0], j + d[1]
                    if 0 <= ni < m and 0 <= nj < n and (board[ni][nj] == 1 or board[ni][nj] == -1):
                        live_neighbors += 1

                if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    board[i][j] = -1 # Transition from live to dead
                elif board[i][j] == 0 and live_neighbors == 3:
                    board[i][j] = 2  # Transition from dead to live

        # Change temporary states back to final states
        for i in range(m):
            for j in range(n):
                if board[i][j] == -1:
                    board[i][j] = 0
                elif board[i][j] == 2:
                    board[i][j] = 1

Explanation

  • The temporary states are used to keep track of the original state while computing the next state. Here, -1 represents a cell that was live but is now dead, and 2 represents a cell that was dead but is now live.
  • The code calculates the next state for each cell based on the rules provided and updates the board in-place.

Key Takeaways

  • The in-place solution avoids using extra space by encoding transitional states.
  • The time complexity is (O(m \times n)), where (m) and (n) are the dimensions of the board.
  • The space complexity is (O(1)), since the board is updated in-place without using additional space.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def game_of_life(board)
  # Offsets to find 8 neighboring cells for a given cell
  neighbors = [[1,0], [1,-1], [0,-1], [-1,-1], [-1,0], [-1,1], [0,1], [1,1]]
  
  rows = board.size
  cols = board[0].size
  
  for row in (0...rows)
    for col in (0...cols)
      live_neighbors = 0

      neighbors.each do |neighbor|
        r = row + neighbor[0]
        c = col + neighbor[1]

        if (r < rows && r >= 0) && (c < cols and c >= 0) && (board[r][c]).abs == 1
          live_neighbors += 1
        end
      end

      if board[row][col] == 1 && (live_neighbors < 2 || live_neighbors > 3)
        board[row][col] = -1
      end

      if board[row][col] == 0 && live_neighbors == 3
        board[row][col] = 2
      end

    end
  end
  
  for row in (0...rows)
    for col in (0...cols)
      if board[row][col] > 0
        board[row][col] = 1
      else
        board[row][col] = 0
      end
    end
  end

end