Candy Crush
Understanding the Problem
This is a simulation problem: implement the elimination mechanic from Candy Crush. We repeat two operations until the board stabilizes: find 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.
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 scan again, and the process repeats until a full scan finds nothing to crush.
The problem breaks down into three 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, the board is stable.
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
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 directly models the game loop: find matches, remove them, drop, check again.
A separate matrix keeps marking and reading cleanly apart: the scan only ever reads candy values from board, and only ever writes marks to crush, so no marking decision can corrupt a later comparison in the same pass.
Algorithm
- Create a boolean matrix
crushof the same size as the board, initialized to allfalse. - Scan every row for windows of three equal non-zero values and mark all three cells as
trueincrush. Do the same for every column. Overlapping windows extend the marks, so a run of four or more is fully covered. - For every cell marked
true, setboard[i][j] = 0. - Apply gravity: for each column, scan from the bottom with a write cursor, copy each non-zero value down to the cursor, then fill everything above the cursor with zeroes.
- If step 2 marked at least one cell, repeat from step 1. Otherwise the board is stable, so return it.
Visualization and Code
Loading animation...
- 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 allocates a fresh boolean matrix every iteration. Candy values are always positive, so the next approach drops the extra matrix and encodes the mark in the sign of each cell instead.
Approach 2: In-Place Simulation with Negation
Intuition
All candy values are positive integers, so negating a value marks it for crushing while abs() still recovers the candy type. The board itself carries the marks, and the separate boolean matrix disappears.
The loop keeps the same shape (mark, crush, drop), with two changes. The marking phase compares absolute values and flips matched cells to negative. The crush and drop phases then merge into a single pass per column that keeps only the positive values and zero-fills the rest, so marked cells never need to be reset to zero explicitly; gravity treats anything non-positive as empty.
Negation preserves the candy type: abs(board[i][j]) recovers the original value, so already-marked cells still participate in later window checks. In a row like [3, 3, 3, 3], checking positions 0-2 negates all three. The next window at positions 1-3 compares abs(-3) == abs(3), detects the match, and negates position 3 as well. Runs longer than three are always fully marked.
Algorithm
- Scan every row: if
abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2])and the value is non-zero, set all three cells to the negated value. Re-negating an already-marked cell writes the same value, so overlapping windows are harmless. - Scan every column with the same logic on
board[i][j],board[i+1][j],board[i+2][j]. - Crush and drop in one pass: for each column, scan from the bottom with a write cursor, copy each positive value down to the cursor, then fill everything above the cursor with zeroes. Negative (marked) and zero cells are overwritten.
- If steps 1-2 negated at least one cell, repeat from step 1. Otherwise the board is stable, so return it.
Visualization and Code
Loading animation...
- 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.