289. Game of Life

https://leetcode.com/problems/game-of-life/

Python

Time: O(m*n+k)
Space: O(k) # k is the matched of rule 1, 3, 4

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

        matches = []   # (row, col, new_value)

        for row in range(m):
            for col in range(n):
                lives = self.count_lives_neighbors(board, row, col)
                if board[row][col] == 1:
                    if lives < 2 or lives > 3:
                        # Rule 1 & 3
                        matches.append((row, col, 0))
                else:
                    # Rule 4
                    if lives == 3:
                        matches.append((row, col, 1))

        for match in matches:
            row, col, value = match
            board[row][col] = value


    @staticmethod
    def count_lives_neighbors(board, row, col):
        count = 0
        for r in range(max(0, row-1), min(row+2, len(board))):
            for c in range(max(0, col-1), min(col+2, len(board[0]))):
                count += board[r][c]
        return count - board[row][col]

Python​

Python