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 = Falsefor 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 = Trueif 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] *= -1if board[i - 1][j] > 0: board[i - 1][j] *= -1if board[i - 2][j] > 0: board[i - 2][j] *= -1crush = Truereturn crushwhile 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)

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] = 0for i in range(R):count = 0board[i] = [x for x in board[i] if x]board[i].extend([0]*(C - len(board[i])))else:breakreturn 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)