Candy Crush - Solution & Explanation

Problem Overview: You’re given a 2D board representing candies. Whenever three or more identical candies appear consecutively in a row or column, they get crushed (set to zero), and the candies above fall down due to gravity. This process repeats until no more matches exist. The goal is to return the final stable board.

Approach 1: Naive Re-scan Simulation (O((m*n)^2) time, O(1) space)

The most direct strategy is to repeatedly scan the grid and remove matches as soon as you find them. Iterate through the matrix, check every cell for horizontal or vertical runs of length ≥ 3, mark them as crushed, then shift candies down column by column. After each crush, run another full scan because new matches may form after gravity applies.

This works but does extra work because the board may change multiple times per iteration. In the worst case, each round only removes a few candies, causing many full rescans. The approach still uses constant extra space because updates happen directly on the board.

Approach 2: Mark-and-Drop Simulation (O(m*n*max(m,n)) time, O(1) space)

A cleaner simulation separates detection and removal. First pass: scan the grid and mark candies that should be crushed instead of removing them immediately. When checking horizontally or vertically, compare absolute values so previously marked cells are still counted. Mark cells by negating their value or using a sentinel. This ensures overlapping groups are handled in the same pass.

Second pass: apply gravity column by column. Use a pointer from the bottom of each column and move surviving candies downward. Fill remaining cells at the top with zeros. This step resembles a compaction pass commonly used in array problems.

Repeat the two phases until no new candies are marked. The key insight is that marking first prevents interference between overlapping matches in the same iteration. Each round processes the entire matrix once for detection and once for gravity.

Recommended for interviews: The mark-and-drop simulation is the expected solution. It shows you can model state changes cleanly while avoiding incorrect partial updates. A brute re-scan demonstrates understanding of the mechanics, but the marking technique proves you can design robust simulations on grid problems.