Candy Crush
Medium · Two Pointers · Explanation and code example
In-place Modification
How it works
Instead of using a separate set to track crushed candies, we can mark them in-place by negating their values. This allows us to identify candies to crush while still being able to check for matching (using absolute values). After marking, we convert all negative values to 0. This reduces space usage compared to maintaining a separate set.
Steps
- Scan the board for groups of three or more adjacent candies. When found, mark them by negating their values (making them negative). Use absolute values when comparing to handle already-marked candies.
- After marking, convert all negative values to
0. - Return a flag indicating whether any candies were marked for crushing.
- Implement the
dropfunction to move non-zero candies down in each column. - Repeat the find-and-crush step followed by
dropuntil no candies are marked for crushing. - Return the final board state.
Complexity
- Time complexity:
O(m^2 × n^2) - Space complexity:
O(1)constant space
Where
m × nis the size of the gridboard
Things to watch for
Only Checking Exactly Three Adjacent Candies
Groups can be longer than three candies. Checking only the center of a triplet misses candies at the ends of longer sequences. The solution must mark all candies in contiguous groups of three or more.
Crushing Before Fully Marking All Matches
If you crush candies immediately upon finding a match, you may miss overlapping horizontal and vertical groups. All crushable candies must be identified first, then crushed together.
Incorrect Drop Logic
When dropping candies, you must process each column from bottom to top, moving non-zero candies down to fill gaps. A common mistake is shifting candies horizontally or not properly tracking the lowest available position.
Python code example
from typing import List
class Solution:
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
m, n = len(board), len(board[0])
def find_and_crush():
complete = True
# Check vertically adjacent candies
for r in range(1, m - 1):
for c in range(n):
if board[r][c] == 0:
continue
if abs(board[r][c]) == abs(board[r - 1][c]) == abs(board[r + 1][c]):
board[r][c] = -abs(board[r][c])
board[r - 1][c] = -abs(board[r - 1][c])
board[r + 1][c] = -abs(board[r + 1][c])
complete = False
# Check horizontally adjacent candies
for r in range(m):
for c in range(1, n - 1):
if board[r][c] == 0:
continue
if abs(board[r][c]) == abs(board[r][c - 1]) == abs(board[r][c + 1]):
board[r][c] = -abs(board[r][c])
board[r][c - 1] = -abs(board[r][c - 1])
board[r][c + 1] = -abs(board[r][c + 1])
complete = False
# Set the value of each candies to be crushed as 0
for r in range(m):
for c in range(n):
if board[r][c] < 0:
board[r][c] = 0
return complete
def drop():
for c in range(n):
lowest_zero = -1
# Iterate over each column
for r in range(m - 1, -1, -1):
if board[r][c] == 0:
lowest_zero = max(lowest_zero, r)
# Swap current non-zero candy with the lowest zero.
elif lowest_zero >= 0:
board[r][c], board[lowest_zero][c] = board[lowest_zero][c], board[r][c]
lowest_zero -= 1
# Continue with the three steps until we can no longer find any crushable candies.
while not find_and_crush():
drop()
return board
C++ code example
class Solution {
int m, n;
bool findAndCrush(vector<vector<int>>& board) {
bool complete = true;
// Check vertically adjacent candies
for (int r = 1; r < m - 1; r++) {
for (int c = 0; c < n; c++) {
if (board[r][c] == 0) {
continue;
}
if (abs(board[r][c]) == abs(board[r - 1][c]) && abs(board[r][c]) == abs(board[r + 1][c])) {
board[r][c] = -abs(board[r][c]);
board[r - 1][c] = -abs(board[r - 1][c]);
board[r + 1][c] = -abs(board[r + 1][c]);
complete = false;
}
}
}
// Check horizontally adjacent candies
for (int r = 0; r < m; r++) {
for (int c = 1; c < n - 1; c++) {
if (board[r][c] == 0) {
continue;
}
if (abs(board[r][c]) == abs(board[r][c - 1]) && abs(board[r][c]) == abs(board[r][c + 1])) {
board[r][c] = -abs(board[r][c]);
board[r][c - 1] = -abs(board[r][c - 1]);
board[r][c + 1] = -abs(board[r][c + 1]);
complete = false;
}
}
}
// Set the value of each candy to be crushed as 0
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (board[r][c] < 0) {
board[r][c] = 0;
}
}
}
return complete;
}
void drop(vector<vector<int>>& board) {
for (int c = 0; c < n; c++) {
int lowestZero = -1;
// Iterate over each column
for (int r = m - 1; r >= 0; r--) {
if (board[r][c] == 0) {
lowestZero = max(lowestZero, r);
} else if (lowestZero >= 0) {
int temp = board[r][c];
board[r][c] = board[lowestZero][c];
board[lowestZero][c] = temp;
lowestZero--;
}
}
}
}
public:
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
m = board.size();
n = board[0].size();
// Continue with the three steps until we can no longer find any crushable candies.
while (!findAndCrush(board)) {
drop(board);
}
return board;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.