⚡Flashcard Drill➔
NeetCode #25LC-723MediumArrays & HashingNC Algo100
← Back to All Problems

#25 · #723 · Candy Crush(粉碎糖果)

📌 Problem Statement & Constraints

Implement Candy Crush on an m x n board of integers (1-3 for candy types, 0 for empty). Repeatedly: (1) mark all candies that are part of a horizontal or vertical run of 3 or more identical values, (2) set all marked cells to 0, (3) let the candies above fall down, preserving their order. Repeat until no more candies can be crushed, then return the board. Constraints: 3 <= m, n <= 50.

💡 Core Algorithmic Approaches

  1. Loop until a full pass produces no changes: mark, crush, then apply gravity.
  2. Marking: scan every horizontal triple (i, j), (i, j+1), (i, j+2) and every vertical triple, collecting the coordinates of runs of length 3 with equal non-zero values into a set.
  3. Using a set for the marked cells avoids double-marking where horizontal and vertical runs intersect.
  4. Gravity: for each column, walk from the bottom up with a write pointer, compacting non-zero values downward, then zero-fill the top.
  5. Termination is guaranteed because each iteration either crushes at least one candy (strictly reducing the count of non-zero cells) or stops.

💻 Benchmark Python3 Implementation

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        m, n = len(board), len(board[0])
        while True:
            crush = set()
            # horizontal runs of 3+
            for i in range(m):
                for j in range(n - 2):
                    v = board[i][j]
                    if v != 0 and v == board[i][j + 1] == board[i][j + 2]:
                        crush |= {(i, j), (i, j + 1), (i, j + 2)}
            # vertical runs of 3+
            for i in range(m - 2):
                for j in range(n):
                    v = board[i][j]
                    if v != 0 and v == board[i + 1][j] == board[i + 2][j]:
                        crush |= {(i, j), (i + 1, j), (i + 2, j)}
            if not crush:
                return board              # stable -> done
            for i, j in crush:
                board[i][j] = 0           # crush
            # gravity: compact each column downward
            for j in range(n):
                write = m - 1
                for i in range(m - 1, -1, -1):
                    if board[i][j] != 0:
                        board[write][j] = board[i][j]
                        write -= 1
                for i in range(write, -1, -1):
                    board[i][j] = 0       # zero-fill the vacated top
        return board

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(iterations * m * n). Each iteration is a full grid scan plus gravity, and each iteration strictly reduces the number of non-zero cells, so the number of iterations is bounded by the number of candies.
💾 Space Complexity
O(m * n) for the crush set in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Crushing and dropping in the same pass without re-checking: gravity can create new runs, so the whole mark-crush-drop cycle must repeat until stable.
  • Forgetting the v != 0 guard: three adjacent empty cells would be treated as a run of zeros.
  • Using a list instead of a set for crush: a cell in both a horizontal and a vertical run would be counted twice (harmless for zeroing, but confusing), and membership tests become O(k).
  • Dropping candies with a bubble-swap loop: O(m^2) per column; the write-pointer compaction is O(m).
  • Returning early after one round: the board may still have crushable runs after the drop.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems