[Top Interview 150] 289. Game of Life

Solution)

 

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # Global Variables
        ROWS, COLS = len(board), len(board[0])

        # Helper func that counts neighbors
        def countNeighbors(r, c):
            nei = 0

            for i in range(r-1, r+2):
                for j in range(c-1, c+2):
                    # Conditions where board[i][j] DNE
                    if ((i==r and j==c) or i < 0 or j < 0 or 
                        i == ROWS or j == COLS):
                        continue
                    
                    # If the neighbor was originally 1
                    if board[i][j] in [1, 3]:
                        nei += 1
            
            return nei

        # Set flags
        for r in range(ROWS):
            for c in range(COLS):
                nei = countNeighbors(r, c)

                if board[r][c]:
                    if nei in [2, 3]:
                        board[r][c] = 3

                elif nei == 3:
                    board[r][c] = 2
        
        # Check flags and convert numbers
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == 1:
                    board[r][c] = 0
                elif board[r][c] in [2, 3]:
                    board[r][c] = 1

 
 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(m*n)
Space Complexity: O(1)
 
 

Explanation)

To modify the board in-place without using extra memory, we need to set up our own truth table.
 
Original    Modified    Flag
     0               0             0   
     1               0             1
     0               1             2
     1               1             3
 
As we iterate the numbers in board,
if the number is 0 and stays as 0, we'll set the flag as 0
if the number is 1 but needs to be modifed to 0, we'll set the flag as 1.
if the number is 0 but needs to be modified to 1, we'll set the flag as 2.
if the number is 1 and stays as 0, we'll set the flag as 3.
 
Using this truth table, we'll convert the numbers into those flags according to their neighbors.
Then we iterate board again, and change the number from Original to Modified according to the flag.
 
 

Helper function)

We'll make a helper function that will count the neighbors of the current number.
 
We check the numbers (neighbors) from r-1 to r+1th row and c-1 to c+1th column.
If the indexes don't go out of bounds, we count the live neighbors. 
 
If the neighbor has a value of either 1 or 3, that means that neighbor was originally a live neighbor.
If the flag is 1, Original 1 to Modified 0.
If the flag is 3, Original 1 to Modified 1.
 
Once we count all the live neghbors, we return that value.
 

def gameOfLife(self, board: List[List[int]]) -> None:
        ROWS, COLS = len(board), len(board[0])

        def countNeighbors(r, c):
            nei = 0

            for i in range(r-1, r+2):
                for j in range(c-1, c+2):
                    if ((i==r and j==c) or i < 0 or j < 0 or 
                        i == ROWS or j == COLS):
                        continue
                    
                    if board[i][j] in [1, 3]:
                        nei += 1
            
            return nei

 
 

Set the flags)

While iterating the numbers, get the count of live neighbors using the helper function.
 
Then we check if the current number is 1 or 0.
 
If it's 1, we check if the count of live neighbors is either 2 or 3.
If the current number is alive and the count of live neighbors is either 2 or 3, the current number will be still alive.
 
Thus we set the current number to the flag 3 (Original 1 -> Modified 1).
 
If the current number is 0, we check if nei is 3. If nei is 3, the dead number becomes alive.
So we set the current number to the flag 2 (Original 0 -> Modified 1).
 
Last condition is where the current number is 1 and nei is more than 3. In this case, the curren number dies. However, since the flag 1 already means that the original 1 becomes 0, we don't need to change anything.
 

def gameOfLife(self, board: List[List[int]]) -> None:
        ROWS, COLS = len(board), len(board[0])

        def countNeighbors(r, c):
            # Helper Function

        for r in range(ROWS):
            for c in range(COLS):
                nei = countNeighbors(r, c)

                if board[r][c]:
                    if nei in [2, 3]:
                        board[r][c] = 3

                elif nei == 3:
                    board[r][c] = 2

 
 

Convert the flags into 1's and 0's)

After setting the flags, it's time to convert those flags into 1's and 0's.
 
1) If the flag is 0, original 0 stayed as 0. Thus, we don't need to change anything.
2) If the flag is 1, original 1 changed to 0. Thus, we change the current flag to 0.
3) If the flag is either 2 or 3, original 0 or 1 changed to 1. Thus we change the current flag to 1.
 

def gameOfLife(self, board: List[List[int]]) -> None:
        ROWS, COLS = len(board), len(board[0])

        def countNeighbors(r, c):
            # Helper Function

        for r in range(ROWS):
            for c in range(COLS):
                nei = countNeighbors(r, c)

                if board[r][c]:
                    if nei in [2, 3]:
                        board[r][c] = 3

                elif nei == 3:
                    board[r][c] = 2
        
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == 1:
                    board[r][c] = 0
                elif board[r][c] in [2, 3]:
                    board[r][c] = 1

 
 
 
I remember doing this problem during lab in university. My approach then was to use extra memory and I couldn't think of other way to do it, so I solved it using O(m*n) space complexity.