Skip to main content
Talentd

Candy Crush - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersMatrixSimulation7 min readAsked at: Meta, Capital One, Visa +8
Practice this problem

Problem Statement

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 board[i][j] == 0 represents that the cell is empty.

The given board represents the state of the game following the player's move. Now, you need to restore the board to a stable state by crushing candies according to the following rules:

  • If three or more candies of the same type are adjacent vertically or horizontally, crush them all at the same time - these positions become empty.
  • After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or bottom at the same time. No new candies will drop outside the top boundary.
  • After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps.
  • If there does not exist more candies that can be crushed (i.e., the board is stable), then return the current board.

You need to perform the above rules until the board becomes stable, then return the stable board.

 

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]]

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]]

 

Constraints:

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

Approach Overview

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.

Solution

We can traverse the matrix row by row and column by column to find three consecutive identical elements and mark them as negative numbers. If marking is successful, we need to move the elements in the matrix down until no elements can move down.

The time complexity is O(m^2 times n^2), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Re-scan SimulationO((m*n)^2)O(1)Simple implementation when correctness matters more than efficiency
Mark-and-Drop SimulationO(m*n*max(m,n))O(1)Optimal simulation approach for grid problems with repeated state updates

Video Solution

LeetCode 723. Candy Crush • Happy Coding • 11,727 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Candy Crush easy or hard?
Candy Crush is rated Medium because the logic is straightforward but the implementation requires careful handling of repeated board updates. Many candidates struggle with correctly marking candies and applying gravity without breaking overlapping matches.
Candy Crush Python/Java solution
Implement the mark-and-drop simulation: scan the board to mark sequences of three or more equal candies horizontally or vertically, negate their values to mark them, then compress each column downward and fill remaining cells with zeros. This logic translates directly to Python, Java, C++, Go, and TypeScript.
How to solve Candy Crush in O(n)?
Candy Crush cannot be solved in strict O(n) time for a general m x n board because each crush operation may cause cascading updates across rows and columns. The practical solution is a simulation that repeatedly scans the board and applies gravity, giving a time complexity around O(m*n*max(m,n)).
What is the best approach for Candy Crush?
The mark-and-drop simulation approach is the most reliable solution. First scan the grid to mark all candies that form horizontal or vertical groups of three or more, then apply gravity to drop remaining candies down each column. Repeat until no more groups exist. This approach runs in O(m*n*max(m,n)) time and uses O(1) extra space.
Is Candy Crush asked at Google/Amazon/Meta?
Grid simulation problems like Candy Crush appear in interviews at companies such as Amazon, Google, and Meta because they test careful implementation and edge-case handling. The question evaluates matrix traversal, state updates, and clean simulation logic.
What data structure is used in Candy Crush?
The main data structure is a 2D array (matrix) representing the game board. The algorithm scans the matrix to detect sequences and then manipulates columns to simulate gravity. No additional complex structures are required beyond the board itself.
What is the time complexity of Candy Crush?
The typical simulation solution runs in O(m*n*max(m,n)) time. Each iteration scans the entire board to detect matches and then performs a gravity pass per column. Since the board can change multiple times before stabilizing, several iterations may occur before no more candies can be crushed.

Ready to solve this problem?

Practice Candy Crush with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays