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
