DSA problem

Candy Crush

MediumMatrix (2D Array)Pattern: Matrix Manipulationtop600AmazonMicrosoftFacebookKingBloomberg

This question is about implementing a basic elimination algorithm for Candy Crush. Given an m x n integer array board representing the grid of candy where board[i][j] represents the type of candy, a value of 0 represents an empty cell.

The given board represents the state of the game following a player move. Now you need to restore the board to a stable state by crushing candies according to two rules. First, if three or more candies of the same type are adjacent vertically or horizontally, crush them all at the same time (set those cells to empty). Second, after crushing, if an empty space causes candies above it to drop down, then candies fall down to fill empty spaces, with cells far away from the bottom falling first. No new candies drop in from the top.

After completing one round of crush and drop, the above process may create more candies that need to be crushed; you must keep repeating the crush-and-drop cycle until no more candies can be crushed. You need to return the stable board.

The intuition for the solution is a two-phase iteration. In the mark phase, scan every cell and look at horizontal and vertical triplets; any candy that is part of a run of three or more is flagged by negating its value (a non-destructive marker that preserves the original type for overlapping runs). In the crush-and-gravity phase, set all flagged cells to zero, then for each column collapse non-zero values toward the bottom. Repeat both phases until a full mark pass finds nothing to crush.

Examples

Example 1

Input:

board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]

Output:

[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

Explanation: Multiple vertical and horizontal runs of three or more identical candies are crushed simultaneously, then surviving candies fall down column by column until the board reaches a stable state with empty cells at the top.

Example 2

Input: board = [[1,3,5,5,2],[3,4,3,3,1],[3,2,4,5,2],[2,4,4,5,5],[1,4,4,1,1]]

Output: [[1,3,0,0,0],[3,4,0,5,2],[3,2,0,3,1],[2,4,0,5,2],[1,4,3,1,1]]

Explanation: The vertical run of three 4s in column 1 and the run in column 2, plus horizontal runs, are crushed; afterward candies drop, and the resulting board has no further runs of three.

Example 3

Input: board = [[1,2,3],[4,5,6],[7,8,9]]

Output: [[1,2,3],[4,5,6],[7,8,9]]

Explanation: No three adjacent candies share the same type, so the board is already stable and is returned unchanged.

Constraints

m == board.length
n == board[i].length
3 <= m, n <= 50
1 <= board[i][j] <= 2000

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

matrixarraysimulationtwo-pointersin-place

Browse all DSA problems