Candy Crush

This problem involves iteratively crushing candies that are adjacent vertically or horizontally (3 or more), and then allowing candies above the crushed ones to drop down. This process continues until no more candies can be crushed.

Here’s a step-by-step explanation of the code to solve this problem:

  1. Find Candies to Crush: For each cell in the board, check if it’s part of a horizontal or vertical line of three or more of the same candy. If so, mark it for crushing. This can be done by setting a temporary board with the negative value of the candy that will be crushed.

  2. Crush the Candies: Iterate through the board, and for each cell marked for crushing, set it to zero.

  3. Drop the Candies: Iterate through each column from the bottom up, shifting non-zero elements downwards.

  4. Repeat Until Stable: Repeat steps 1-3 until no more candies can be crushed.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        if not board:
            return []

        m, n = len(board), len(board[0])
        found = True

        # Continue until no more candies to crush
        while found:
            crush = [[0] * n for _ in range(m)]
            found = False

            # Mark candies for crushing
            for i in range(m):
                for j in range(n - 2):
                    if abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]) != 0:
                        crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = 1
                        found = True

            for i in range(m - 2):
                for j in range(n):
                    if abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]) != 0:
                        crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = 1
                        found = True

            # Crush the candies
            for i in range(m):
                for j in range(n):
                    if crush[i][j]:
                        board[i][j] = 0

            # Drop the candies
            for j in range(n):
                idx = m - 1
                for i in range(m - 1, -1, -1):
                    if board[i][j] != 0:
                        board[idx][j] = board[i][j]
                        idx -= 1
                for i in range(idx, -1, -1):
                    board[i][j] = 0

        return board

This code will handle the entire process of identifying crushable candies, crushing them, dropping the candies above, and repeating this process until the board is stable.