Detail of drop:
class Solution:
'''
1. Find: Use hashset store crushed candy
2. Crush: changed crushed candy to 0
3. Drop: use idx point to the end of col, enumerate from the end of col
when num in col != 0, swap with idx
T: O(mn), S(Omn)
Or:
When find candy, change it to negative, use flag to determine break
S:(Omn) -> O(1)
'''
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
m, n = len(board), len(board[0])
while True:
crush = set()
# 1. Find
for i in range(m):
for j in range(n):
if i >= 2 and board[i][j] and board[i][j] == board[i-1][j] == board[i-2][j]:
crush.add((i,j))
crush.add((i-1,j))
crush.add((i-2,j))
if j >= 2 and board[i][j] and board[i][j] == board[i][j-1] == board[i][j-2]:
crush.add((i,j))
crush.add((i,j-1))
crush.add((i,j-2))
# 2. Crush
if not crush:
break
for i,j in crush:
board[i][j] = 0
print(board)
# 3. Drop
for j in range(n):
idx = m-1
for i in range(m-1, -1, -1):
if board[i][j] != 0:
board[i][j], board[idx][j] = board[idx][j], board[i][j]
idx-=1
return board