Candy Crush
Last Updated: April 2, 2026
Understanding the Problem
This is a simulation problem that models how Candy Crush works behind the scenes. We need to repeatedly perform two operations until the board stabilizes: first, find and mark all groups of three or more identical candies in a row (horizontally or vertically), then crush them all at once and let gravity pull the remaining candies downward.
The tricky part is that crushing must happen simultaneously. You can't crush one group, drop, then look for the next group in the same iteration. All crushable candies in a given round must be identified before any of them are removed. After removal and gravity, you check again. The process repeats until a full scan finds nothing to crush.
The key observation is that this problem breaks down into three clean sub-problems that we loop over: mark (find all crushable candies), crush (set them to zero), and drop (apply gravity column by column). Once a full mark phase finds zero candidates, we're done.
Key Constraints:
3 <= m, n <= 50→ The board is small, at most 2,500 cells. Even O(m^2 * n^2) per iteration would be fast enough. Efficiency isn't a concern here, clarity and correctness are.1 <= board[i][j] <= 2000→ Candy values are always positive. This means we can use negative values as markers without conflicting with actual candy types.
Approach 1: Simulation with Boolean Marking
Intuition
The most straightforward approach: use a separate boolean matrix to track which cells need to be crushed. Scan every cell to see if it's part of a horizontal or vertical run of three or more identical candies. Mark all such cells in the boolean matrix, crush them (set to 0), apply gravity, and repeat.
This is the approach you'd naturally come up with if you just followed the problem description step by step. It directly models the game loop: find matches, remove them, drop, check again.
Algorithm
- Create a boolean matrix
crushof the same size as the board, initialized to allfalse. - Scan every cell. For each cell, check if it starts a horizontal run of 3+ identical values, or a vertical run of 3+ identical values. If so, mark all cells in that run as
truein thecrushmatrix. - If no cells were marked, the board is stable. Return it.
- For every cell marked
true, setboard[i][j] = 0. - Apply gravity: for each column, collect all non-zero values, pack them to the bottom, fill the top with zeroes.
- Go back to step 1.
Example Walkthrough
Code
- Time Complexity: O(k m n) where k is the number of iterations until the board stabilizes. Each iteration scans the entire board O(m n) to find matches and applies gravity O(m n). The number of iterations k is bounded by (m * n) / 3 since each iteration removes at least 3 candies.
- Space Complexity: O(m * n). We allocate a boolean matrix of the same size as the board in each iteration.
This approach works correctly but allocates a fresh boolean matrix every iteration. Since all candy values are positive, what if we used the sign of each value as a built-in flag to mark cells for crushing?
Approach 2: In-Place Simulation with Negation
Intuition
Since all candy values are positive integers, we can negate a value to mark it for crushing while still being able to read its candy type via abs(). This eliminates the need for a separate boolean matrix entirely.
The algorithm follows the same three-phase loop (mark, crush, drop), but the marking phase now flips values to negative instead of writing to a separate array. When checking if adjacent cells match, we compare absolute values so that already-marked cells still participate in matching. After marking, any cell with a negative value gets set to 0, and gravity drops the rest down.
The negation trick works because it's reversible and non-destructive. When we negate board[i][j], we can still recover the candy type with abs(board[i][j]). This means cells that have already been marked can still participate in matching, which is critical. Consider a row like [3, 3, 3, 3]. When we check positions 0-2, we negate all three. When we then check positions 1-3, position 1 is already negative, but abs(-3) == abs(3), so the match is correctly detected and position 3 gets negated too. All four cells end up marked.
Algorithm
- Scan every cell for horizontal runs: if
abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2])and the value is non-zero, negate all three cells (if not already negative). - Scan every cell for vertical runs: same logic but checking
board[i][j],board[i+1][j],board[i+2][j]. - If no cells were negated, the board is stable. Return it.
- Apply gravity: for each column, use a two-pointer approach. Scan from bottom to top, moving only positive (non-zero, non-marked) values downward and filling the top with zeroes.
- Repeat from step 1.
Example Walkthrough
Code
- Time Complexity: O(k m n) where k is the number of iterations until the board stabilizes. Each iteration does O(m n) work for marking and O(m n) for gravity. The maximum number of iterations is bounded by (m * n) / 3 since each iteration removes at least 3 candies.
- Space Complexity: O(1) extra space. We mark cells directly on the board using negation, so no additional data structures are needed beyond the input.