Python solution using a stack


  • 0
    B

    After coming up with this, I see people taken advantage of the expected values and using other parts to store the next state. Then going on to use a bitwise operations to get the the next state. That did not occur to me. I used a stack to keep track of the cell that needed to be updated and then updating after all cells are evaluated. This is not a solution for the infinite follow up question. Please let me know what you think.

    class Solution(object):
        def gameOfLife(self, board):
            def getNeighbors(i,j, n, m, b):
                neighbors = 0
                # above
                if i > 0:
                    if j > 0: neighbors += b[i-1][j-1]
                    if j+1 < m: neighbors += b[i-1][j+1]
                    neighbors += b[i-1][j]
                # inline 
                if j > 0: neighbors += b[i][j-1] 
                if j+1 < m: neighbors += b[i][j+1]
                # below
                if i+1 < n:
                    neighbors += b[i+1][j]
                    if j > 0: neighbors += b[i+1][j-1]
                    if j+1 < m: neighbors += b[i+1][j+1]
                return neighbors
                
            n = len(board)
            m = len(board[0])
            stack = []
            for i, row in enumerate(board):
                for j, cell in enumerate(row):
                    neighbors = getNeighbors(i, j, n, m, board)
                    if cell:
                        if neighbors < 2 or neighbors > 3:
                            stack.append((i,j,0))
                    else:
                        if neighbors == 3:
                            stack.append((i,j,1))
            while stack:
                top = stack.pop()
                board[top[0]][top[1]] = top[2]
    

    Thank you!


Log in to reply
 

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