very simple to understand 3 - pass O(mn) time and O(1) space


  • 0
    S
    class Solution(object):
        def gameOfLife(self, board):
            """
            :type board: List[List[int]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            m = len(board)
            n = len(board[0]) if m > 0 else 0
            if m and n:
                # mark which are alive and which are dead, +ve alive, -ve dead
                # also mark how many neighbors are alive in each cell
                for i in range(m):
                    for j in range(n):
                        neighbors = [(i-1,j-1),(i+1,j+1),(i-1,j+1),(i+1,j-1),(i-1,j),(i+1,j),(i,j-1),(i,j+1)]
                        live      = 0
                        for x,y in neighbors:
                            if 0 <= x < m and 0 <= y < n:
                                if board[x][y] > 0:
                                    live += 1
                        if live:
                            board[i][j] = live if board[i][j] > 0 else -live
                
                # kill or liven the cells depending on rules
                for i in range(m):
                    for j in range(n):
                        if board[i][j] > 0:
                            if board[i][j] < 2 or board[i][j] > 3 : 
                                board[i][j] = -board[i][j]
                        else:
                            if abs(board[i][j]) == 3:
                                board[i][j] = -board[i][j]
                
                # positive becomes 1 and negative becomes 0
                for i in range(m):
                    for j in range(n):
                        if board[i][j] > 0:
                            board[i][j] = 1
                        else:
                            board[i][j] = 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.