The Candy Crush problem on Leetcode provides you with a 2D board of integers, where each integer represents a type of candy. The goal is to repeatedly "crush" (remove) any group of three or more adjacent candies of the same type, either horizontally or vertically. After crushing, candies above will fall down to fill the emptied spaces (gravity), and zeros will fill the top. This process repeats until no more candies can be crushed. The final board should be returned.
board of size m x n.At first glance, you might consider iterating through the board and crushing candies as you find them. However, candies can be part of multiple crushes in a single round, and after gravity, new crushes may become possible. This suggests a need for:
A brute-force approach would be to check every cell for crushes, crush immediately, and then re-scan. However, this can lead to missing overlapping crushes or repeated work. Instead, we look for an optimized approach where we:
Let's break down the solution step-by-step:
We use in-place marking to avoid extra space, and the process is repeated until no more crushes are possible.
Suppose we have the following 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]
]
Each step ensures all crushes are found and gravity is applied before checking for new crushes.
The approach is efficient because each round guarantees at least one candy is crushed, and the board size is limited.
The Candy Crush problem requires repeated simulation of matching, crushing, and gravity. The key insight is to mark all crushable candies in a pass before applying gravity, ensuring all overlaps are handled correctly. By working in-place and repeating until stable, we achieve both correctness and efficiency. This approach elegantly models the actual game mechanics and avoids unnecessary rescans or data structures.
class Solution:
def candyCrush(self, board):
m, n = len(board), len(board[0])
changed = True
while changed:
changed = False
# Mark candies to crush
for i in range(m):
for j in range(n-2):
v = abs(board[i][j])
if v != 0 and v == abs(board[i][j+1]) and v == abs(board[i][j+2]):
board[i][j] = board[i][j+1] = board[i][j+2] = -v
changed = True
for j in range(n):
for i in range(m-2):
v = abs(board[i][j])
if v != 0 and v == abs(board[i+1][j]) and v == abs(board[i+2][j]):
board[i][j] = board[i+1][j] = board[i+2][j] = -v
changed = True
# Gravity
for j in range(n):
write_row = m-1
for i in range(m-1, -1, -1):
if board[i][j] > 0:
board[write_row][j] = board[i][j]
write_row -= 1
for i in range(write_row, -1, -1):
board[i][j] = 0
return board
class Solution {
public:
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
int m = board.size(), n = board[0].size();
bool changed = true;
while (changed) {
changed = false;
// Mark candies to crush
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n - 2; ++j) {
int v = abs(board[i][j]);
if (v != 0 && v == abs(board[i][j+1]) && v == abs(board[i][j+2])) {
board[i][j] = board[i][j+1] = board[i][j+2] = -v;
changed = true;
}
}
}
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m - 2; ++i) {
int v = abs(board[i][j]);
if (v != 0 && v == abs(board[i+1][j]) && v == abs(board[i+2][j])) {
board[i][j] = board[i+1][j] = board[i+2][j] = -v;
changed = true;
}
}
}
// Gravity
for (int j = 0; j < n; ++j) {
int write_row = m - 1;
for (int i = m - 1; i >= 0; --i) {
if (board[i][j] > 0) {
board[write_row--][j] = board[i][j];
}
}
for (int i = write_row; i >= 0; --i) {
board[i][j] = 0;
}
}
}
return board;
}
};
class Solution {
public int[][] candyCrush(int[][] board) {
int m = board.length, n = board[0].length;
boolean changed = true;
while (changed) {
changed = false;
// Mark candies to crush
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n - 2; ++j) {
int v = Math.abs(board[i][j]);
if (v != 0 && v == Math.abs(board[i][j+1]) && v == Math.abs(board[i][j+2])) {
board[i][j] = board[i][j+1] = board[i][j+2] = -v;
changed = true;
}
}
}
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m - 2; ++i) {
int v = Math.abs(board[i][j]);
if (v != 0 && v == Math.abs(board[i+1][j]) && v == Math.abs(board[i+2][j])) {
board[i][j] = board[i+1][j] = board[i+2][j] = -v;
changed = true;
}
}
}
// Gravity
for (int j = 0; j < n; ++j) {
int write_row = m - 1;
for (int i = m - 1; i >= 0; --i) {
if (board[i][j] > 0) {
board[write_row--][j] = board[i][j];
}
}
for (int i = write_row; i >= 0; --i) {
board[i][j] = 0;
}
}
}
return board;
}
}
var candyCrush = function(board) {
let m = board.length, n = board[0].length;
let changed = true;
while (changed) {
changed = false;
// Mark candies to crush
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n - 2; ++j) {
let v = Math.abs(board[i][j]);
if (v !== 0 && v === Math.abs(board[i][j+1]) && v === Math.abs(board[i][j+2])) {
board[i][j] = board[i][j+1] = board[i][j+2] = -v;
changed = true;
}
}
}
for (let j = 0; j < n; ++j) {
for (let i = 0; i < m - 2; ++i) {
let v = Math.abs(board[i][j]);
if (v !== 0 && v === Math.abs(board[i+1][j]) && v === Math.abs(board[i+2][j])) {
board[i][j] = board[i+1][j] = board[i+2][j] = -v;
changed = true;
}
}
}
// Gravity
for (let j = 0; j < n; ++j) {
let write_row = m - 1;
for (let i = m - 1; i >= 0; --i) {
if (board[i][j] > 0) {
board[write_row--][j] = board[i][j];
}
}
for (let i = write_row; i >= 0; --i) {
board[i][j] = 0;
}
}
}
return board;
};