Leetcode # 723. Candy Crush

Problem

https://leetcode.com/problems/candy-crush

Solution

one_turn() := find() + crush() + drop()
m, n := len(board), len(board[0])

Time Complexity: O(m * n)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
    m, n = len(board), len(board[0])
    
    def one_turn():
      crushed = False
      # crush
      def crush(i, j):
        board[i][j] = 0
        nonlocal crushed
        crushed = True

      # find
      for i in range(m):
        pre_candy_j = 0
        for j in range(1, n + 1):
          if j == n or board[i][j] != board[i][pre_candy_j]:
            if board[i][pre_candy_j] != 0 and j - pre_candy_j >= 3:
              for k in range(pre_candy_j, j):
                board[i][k] *= -1
            pre_candy_j = j
    
      for j in range(n):
        pre_candy_i = 0
        for i in range(1, m + 1):
          if i == m or abs(board[i][j]) != abs(board[pre_candy_i][j]):
            if board[pre_candy_i][j] != 0 and i - pre_candy_i >= 3:
              for k in range(pre_candy_i, i):
                crush(k, j)
            else: 
              for k in range(pre_candy_i, i):
                if board[k][j] < 0:
                  crush(k, j)
            pre_candy_i = i
    
        # drop
        p1 = m - 1
        while p1 >= 0:
          if board[p1][j] != 0:
            p1 -= 1
            continue
          p2 = p1 - 1
          while p2 >= 0:
            if board[p2][j] != 0:
              break
            p2 -= 1
          if p2 < 0:
            break
          board[p1][j], board[p2][j] = board[p2][j], 0
          p1 -= 1

      return crushed
    
    while one_turn(): pass
    # for row in board: print([str(candy).rjust(5) for candy in row])
    return board

Last Updated on 2023/08/24 by A1go