Python solution with detailed explanation


  • 0
    G

    Solution

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

    Brute Force - Not in-place solution
    Solution 1 we maintain a list of co-ordinates which must be inverted for next round. This is not an inplace solution.

    class Solution(object):
        def nbr_process(self, x, y, board):
            M, N = len(board), len(board[0])
            candidate, live = [(x,y-1), (x,y+1), (x-1,y), (x+1,y), (x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)], 0
            for x1,y1 in candidate:
                if 0<=x1<M and 0<=y1<N and board[x1][y1] == 1:
                    live += 1
            return live
        
        def gameOfLife(self, board):
            """
            :type board: List[List[int]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            M, N = len(board), len(board[0])
            result = []
            for i in range(M):
                for j in range(N):
                    live = self.nbr_process(i,j,board)
                    if board[i][j] == 1 and (live < 2 or live > 3):
                        result.append((i,j))
                    if board[i][j] == 0 and live == 3:
                        result.append((i,j))
            for a,b in result:
                board[a][b] = board[a][b] ^ 1
            return
    

    Optimized In-place Solution
    Solution 2 we mark the inverted nodes with 2 and 3 which signify a meaning for this life and consequence in next life.

    class Solution(object):
        def nbr_process(self, x, y, board):
            M, N = len(board), len(board[0])
            candidate, live = [(x,y-1), (x,y+1), (x-1,y), (x+1,y), (x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)], 0
            for x1,y1 in candidate:
                if 0<=x1<M and 0<=y1<N and (board[x1][y1] == 1 or board[x1][y1] == 2):
                    live += 1
            return live
        
        def gameOfLife(self, board):
            """
            :type board: List[List[int]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            M, N = len(board), len(board[0])
            for i in range(M):
                for j in range(N):
                    live = self.nbr_process(i,j,board)
                    if board[i][j] == 1 and (live < 2 or live > 3):
                        board[i][j] = 2 # 2 means it is alive now but will be dead next round
                    if board[i][j] == 0 and live == 3:
                        board[i][j] = 3 # 3 means it is dead now but will be alive next round
            for i in range(M):
                for j in range(N):
                    if board[i][j] == 2:
                        board[i][j] = 0
                    if board[i][j] == 3:
                        board[i][j] = 1
            return
    

    https://discuss.leetcode.com/topic/26236/infinite-board-solution
    For the second follow-up question, here's a solution for an infinite board. Instead of a two-dimensional array of ones and zeros, I represent the board as a set of live cell coordinates.


Log in to reply
 

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