Problem statement

https://binarysearch.com/problems/Conway's-Game-of-Life/

Solution

Equal to Leetcode 0289. Game of Life.

Complexity

Time complexity is O(mn), where m and n sizes of our board. However note, that it we do not need to find alive set fist, then we have complexity O(A), where A is number of alive points on given iteration. Space complexity is O(A) as well.

Code

class Solution:
    def solve(self, board):
        m, n = len(board), len(board[0])
        alive = set([(i, j) for i, j in product(range(m), range(n)) if board[i][j] == 1])
        neibs = list(product(range(-1, 2), range(-1, 2)))
        
        count = Counter()
        
        for i, j in alive:
            for dx, dy in neibs:
                count[(i+dx,j+dy)] += 1
                
        for x, y in count:
            if 0 <= x < m and 0 <= y < n:
                if count[x, y] == 3 and board[x][y] == 0: board[x][y] = 1
                if count[x, y] not in [3, 4]: board[x][y] = 0

        return board