Problem statement

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

Solution

In is not obviously stated in problem, but actually all the moved done at once: so, if some candy in horizontal or vertical line of 3, it is removed. Then it is done several times. So, the algorithm will consist of 2 stages:

  1. Create set of coordinates we need to delete: we iterate over table and look for horizontal and vertical sets of 3 equal candies.
  2. Then we iterate over each column and keep only candies we need to leave and add zeroes at the beginning of it (because the top most row is zero row).

Complexity

Time complexity is (m^2n^2), because we can do O(mn) iterations with O(mn) complexity of each iteration. Space complexity is O(mn).

Code

class Solution:
    def candyCrush(self, board):
        m, n = len(board), len(board[0])
        to_delete, crush = set(), False
        for i in range(m):
            for j in range(n):
                v = board[i][j]
                if v == 0: continue
                if 0 < j < n-1 and board[i][j+1] == v and board[i][j-1] == v:
                    crush = True
                    to_delete |= set([(i, j), (i, j+1), (i, j-1)])
                if 0 < i < m-1 and board[i-1][j] == v and board[i+1][j] == v:
                    crush = True
                    to_delete |= set([(i, j), (i+1, j), (i-1, j)])
        
        for j in range(n):
            column = []
            for i in range(m):
                if (i, j) not in to_delete:
                    column.append(board[i][j])
            column = [0] * (m - len(column)) + column
            
            for i in range(m):
                board[i][j] = column[i]
                
        return self.candyCrush(board) if crush else board