Candy Crush
Asked at Roblox
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.
Asked At
| 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.