723. Candy Crush
Asked at Roblox
Difficulty
Medium
Time
O((m * n)^2)
Space
O(1)
Pattern
Array
Companies
1
Problem
You are given an m x n grid called board. Each cell holds an integer that names a candy type. The value 0 means the cell is empty.
The board is the state right after a player's move. Your job is to keep applying the game rules until nothing can change, then return the final board. One round works like this: first, find every group of three or more equal candies that sit in a straight horizontal or vertical line, and crush them all at the same time (those cells become 0). Then let candies fall: in each column, any candy with empty space below it drops straight down until it lands on another candy or on the bottom row. No new candy appears from above.
After a round, new groups may have formed, so you repeat the whole process. When a full round finds no group to crush, the board is stable — return it.
Crush, then drop, then repeat
Constraints
- ●
m == board.length - ●
n == board[i].length - ●
3 <= m, n <= 50 - ●
1 <= board[i][j] <= 2000
Examples
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]][[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]]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]][[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]]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Roblox | Medium | View all Roblox questions → |
How to Think About It
All crushes in one round happen simultaneously. If you clear cells while scanning, you break runs that should also have been detected — so mark first, then clear.
Key trick for marking: negate the value of every candy that belongs to a run (board[r][c] = -abs(v)). Negative cells still compare equal by absolute value, so overlapping horizontal and vertical runs are all detected.
Gravity: process each column bottom-up with a write pointer. Copy every positive value down to the write pointer, then fill the remaining top cells with 0.
Repeat rounds until a round marks nothing.
Complexity per round is O(m * n); the number of rounds is bounded by how many candies can be crushed, so the total is O((m * n)²) in the worst case, which is fine for the 50x50 limit.
Optimal Approach
Step 1: Loop:
found = false.
Horizontal pass: for each r and c with c + 2 < n, let v = abs(board[r][c]); if v != 0 and the next two cells have the same absolute value, negate all three and set found = true.
Vertical pass: the same for r + 2 < m.
If not found, return the board.
Gravity: for each column, move positive values down with a write pointer and zero-fill the rest.
Time: O((m * n)²) worst case. Space: O(1) extra.
Mark, clear, then let gravity work
What Trips People Up in Real Interviews
Crushing cells during the scan. A candy can be part of both a horizontal and a vertical run; clearing early hides the second run.
Comparing raw values after marking. Marked cells are negative — compare absolute values so marked cells still extend runs.
Treating 0 (empty) as a candy type. Three empty cells in a row are not a match.
Doing only one round. Falling candies can create new runs, so loop until nothing changes.
Solution Code
O((m * n)^2) timedef candyCrush(board):
m, n = len(board), len(board[0])
while True:
found = False
for r in range(m):
for c in range(n - 2):
v = abs(board[r][c])
if v and v == abs(board[r][c + 1]) == abs(board[r][c + 2]):
board[r][c] = board[r][c + 1] = board[r][c + 2] = -v
found = True
for r in range(m - 2):
for c in range(n):
v = abs(board[r][c])
if v and v == abs(board[r + 1][c]) == abs(board[r + 2][c]):
board[r][c] = board[r + 1][c] = board[r + 2][c] = -v
found = True
if not found:
return board
for c in range(n):
w = m - 1
for r in range(m - 1, -1, -1):
if board[r][c] > 0:
board[w][c] = board[r][c]
w -= 1
for r in range(w, -1, -1):
board[r][c] = 0Frequently Asked Questions
What is the Candy Crush problem?
Candy Crush asks you to simulate the elimination rules of the game on a grid: any horizontal or vertical run of three or more identical candies is crushed at the same time, candies above empty cells fall down, and the process repeats until the board is stable. It is a pure simulation question that tests careful, bug-free grid code.
How do you solve Candy Crush?
The optimal approach runs in O((m * n)^2) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Candy Crush?
Candy Crush is asked at Roblox. It is a medium difficulty problem.
What are common mistakes on Candy Crush?
- Crushing cells during the scan. A candy can be part of both a horizontal and a vertical run; clearing early hides the second run.
- Comparing raw values after marking. Marked cells are negative — compare absolute values so marked cells still extend runs.
- Treating 0 (empty) as a candy type. Three empty cells in a row are not a match.
- Doing only one round. Falling candies can create new runs, so loop until nothing changes.