723. Candy Crush

Approach 1: Brute Force

class Solution(object):
    def candyCrush(self, board):
        """
        :type board: List[List[int]]
        :rtype: List[List[int]]
        """
        m, n = len(board), len(board[0])
        def gravity():
            for j in range(n):
                stack = [board[i][j] for i in range(m - 1, -1, -1) if board[i][j] > 0]
                stack += [0] *  (m - len(stack))
                for i in range(m): board[i][j] = stack.pop()
        def crush():
            crush = False
            for i in range(m):
                for j in range(n):
                    if j > 1 and board[i][j] > 0 and board[i][j] == abs(board[i][j - 1]) == abs(board[i][j - 2]):
                        board[i][j - 2:j + 1] = [-abs(board[i][j]) for _ in range(3)]
                        crush = True
                    if i > 1 and board[i][j] != 0 and abs(board[i][j]) == abs(board[i - 1][j]) == abs(board[i - 2][j]):
                        if board[i][j] > 0: board[i][j] *= -1
                        if board[i - 1][j] > 0: board[i - 1][j] *= -1
                        if board[i - 2][j] > 0: board[i - 2][j] *= -1
                        crush = True
            return crush  
        while crush(): gravity()
        return board

Find all the values to be deleted and make them negative and then remove all the negative values from the columns one by one

Time Complexity: O(M*N*C) where C is the number of crushing rounds req

Space Complexity: O(M*N)

Approach 2: Rotate array to ease gravity

class Solution(object):
    def candyCrush(self, board):
        """
        :type board: List[List[int]]
        :rtype: List[List[int]]
        """
        board = map(list,zip(*reversed(board)))
        R, C = len(board), len(board[0])
        while True:
            remove = set()
            for i in range(R):
                for j in range(2, C):
                    if board[i][j] != 0 and board[i][j] == board[i][j-1] == board[i][j-2]:
                        remove |= {(i,j), (i,j-1), (i,j-2)}
            for j in range(C):
                for i in range(2, R):
                    if board[i][j] != 0 and board[i][j] == board[i-1][j] == board[i-2][j]:
                        remove |= {(i,j), (i-1,j), (i-2,j)}
            if remove:
                for i,j in remove: board[i][j] = 0
                for i in range(R):
                    count = 0
                    board[i] = [x for x in board[i] if x]
                    board[i].extend([0]*(C - len(board[i])))
            else:
                break
        return list(reversed(map(list,zip(*board))))

After iterating over all rows and columns each time to find a continuous block of candies to remove, we make them zero. Now instead of having a "gravity" function what made sense was to actually rotate the array counter clockwise and shift each of the items in the row left instead of down in a column.

Time Complexity: O(M*N*C) where C is the number of crushing rounds req

Space Complexity: O(M*N)