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

Let us solve the case of infinite board, which I think is the most interesting. Let us do it, using the following steps:

  1. Let us find all alive cells first.
  2. Define list of neigbors: let us count 8 of them + we put the cell itself.
  3. Now, for each alive cell we calculate number of active neigbours.
  4. If it happens, that number of neigbours is equal to 3 and original cell is empty, then we need to make it alive.
  5. If number of neigbours is not 2 or 3 (that is not 3 or 4 using also cell itself), then we need to make this cell dead.

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.

class Solution:
    def gameOfLife(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

If you like the solution, you can upvote it on leetcode discussion section: Problem 0289