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.
Problem Statement
The problem is to implement a basic elimination algorithm for Candy Crush. The input is 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 goal is 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 the 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, repeat the above steps.
If there does not exist more candies that can be crushed (i.e., the board is stable), return the current board.
The output should be the stable board. The algorithm should be able to handle boards of arbitrary size, and there should be no constraints on the
time or space complexity of the solution.
Can you provide an example input and output for this problem?
Can we assume that the board will always be rectangular (i.e., m x n dimensions)?
What should be returned if the initial board is already stable?
Are there any restrictions on the time complexity or space complexity of the solution?
Are there any constraints on the size of the input array, or can it be arbitrarily large?
Solutions
Brute Force Approach:
The simplest approach is to iterate over every cell on the board and check if it can be crushed by checking its neighbors. If any cell is crushed,
repeat the process until the board becomes stable. This approach has a time complexity of O(n^3), where n is the size of the board, making it
impractical for large inputs.
Algorithm:
While there are still candies that can be crushed:
Iterate over every cell in the board:
If the cell has a candy of the same type as its neighboring cells, mark it for crushing.
If any cells were marked for crushing:
Crush all marked cells.
Shift candies down to fill gaps.
Return the stabilized board.
public int[][] CandyCrush(int[][] board) {
int rows = board.Length;
int cols = board[0].Length;
bool hasCrush = true;
while (hasCrush) { // continue crushing candies until there are no more to be crushed
hasCrush = false;
// mark candies to be crushed
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int candy = Math.Abs(board[i][j]);
if (candy == 0) continue; // empty cell, skip
// check horizontally
if (j < cols - 2 && Math.Abs(board[i][j+1]) == candy && Math.Abs(board[i][j+2]) == candy) {
hasCrush = true;
int k = j;
while (k < cols && Math.Abs(board[i][k]) == candy) {
board[i][k++] = -candy; // mark candy for crushing
}
}
// check vertically
if (i < rows - 2 && Math.Abs(board[i+1][j]) == candy && Math.Abs(board[i+2][j]) == candy) {
hasCrush = true;
int k = i;
while (k < rows && Math.Abs(board[k][j]) == candy) {
board[k++][j] = -candy; // mark candy for crushing
}
}
}
}
if (hasCrush) {
// crush marked candies and shift down
for (int j = 0; j < cols; j++) {
int bottom = rows - 1; // bottom non-empty cell
for (int i = rows - 1; i >= 0; i--) {
if (board[i][j] > 0) {
board[bottom--][j] = board[i][j]; // shift down candy
}
}
while (bottom >= 0) {
board[bottom--][j] = 0; // fill rest of column with zeros
}
}
}
}
return board;
}
def candyCrush(board: List[List[int]]) -> List[List[int]]:
rows, cols = len(board), len(board[0])
hasCrush = True
while hasCrush: # continue crushing candies until there are no more to be crushed
hasCrush = False
# mark candies to be crushed
for i in range(rows):
for j in range(cols):
candy = abs(board[i][j])
if candy == 0: continue # empty cell, skip
# check horizontally
if j < cols - 2 and abs(board[i][j+1]) == candy and abs(board[i][j+2]) == candy:
hasCrush = True
k = j
while k < cols and abs(board[i][k]) == candy:
board[i][k] = -candy # mark candy for crushing
k += 1
# check vertically
if i < rows - 2 and abs(board[i+1][j]) == candy and abs(board[i+2][j]) == candy:
hasCrush = True
k = i
while k < rows and abs(board[k][j]) ==
candy:
board[k][j] = -candy # mark candy for crushing
k += 1
if hasCrush:
# crush marked candies and shift down
for j in range(cols):
bottom = rows - 1 # bottom non-empty cell
for i in range(rows-1, -1, -1):
if board[i][j] > 0:
board[bottom][j] = board[i][j] # shift down candy
bottom -= 1
while bottom >= 0:
board[bottom][j] = 0 # fill rest of column with zeros
return board
### Java
```java
public int[][] candyCrush(int[][] board) {
int rows = board.length;
int cols = board[0].length;
boolean hasCrush = true;
while (hasCrush) { // continue crushing candies until there are no more to be crushed
hasCrush = false;
// mark candies to be crushed
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int candy = Math.abs(board[i][j]);
if (candy == 0) continue; // empty cell, skip
// check horizontally
if (j < cols - 2 && Math.abs(board[i][j+1]) == candy && Math.abs(board[i][j+2]) == candy) {
hasCrush = true;
int k = j;
while (k < cols && Math.abs(board[i][k]) == candy) {
board[i][k++] = -candy; // mark candy for crushing
}
}
// check vertically
if (i < rows - 2 && Math.abs(board[i+1][j]) == candy && Math.abs(board[i+2][j]) == candy) {
hasCrush = true;
int k = i;
while (k < rows && Math.abs(board[k][j]) == candy) {
board[k++][j] = -candy; // mark candy for crushing
}
}
}
}
if (hasCrush) {
// crush marked candies and shift down
for (int j = 0; j < cols; j++) {
int bottom = rows - 1; // bottom non-empty cell
for (int i = rows - 1; i >= 0; i--) {
if (board[i][j] > 0) {
board[bottom--][j] = board[i][j]; // shift down candy
}
}
while (bottom >= 0) {
board[bottom--][j] = 0; // fill rest of column with zeros
}
}
}
}
return board;
}
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
int rows = board.size();
int cols = board[0].size();
bool hasCrush = true;
while (hasCrush) { // continue crushing candies until there are no more to be crushed
hasCrush = false;
// mark candies to be crushed
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int candy = abs(board[i][j]);
if (candy == 0) continue; // empty cell, skip
// check horizontally
if (j < cols - 2 && abs(board[i][j+1]) == candy && abs(board[i][j+2]) == candy) {
hasCrush = true;
int k = j;
while (k < cols && abs(board[i][k]) == candy) {
board[i][k++] = -candy; // mark candy for crushing
}
}
// check vertically
if (i < rows - 2 && abs(board[i+1][j]) == candy && abs(board[i+2][j]) == candy) {
hasCrush = true;
int k = i;
while (k < rows && abs(board[k][j]) == candy) {
board[k++][j] = -candy; // mark candy for crushing
}
}
}
}
if (hasCrush) {
// crush marked candies and shift down
for (int j = 0; j < cols; j++) {
int bottom = rows - 1; // bottom non-empty cell
for (int i = rows - 1; i >= 0; i--) {
if (board[i][j] > 0) {
board[bottom--][j] = board[i][j]; // shift down candy
}
}
while (bottom >= 0) {
board[bottom--][j] = 0; // fill rest of column with zeros
}
}
}
}
return board;
}
Time complexity: O((mn)^3)
Space complexity: O(1) (no extra space used)
Depth-First Search (DFS) Approach:
DFS is another approach that can be used to solve this problem. We can use DFS to identify groups of adjacent candies that have the same color,
and then remove them. After removing the candies, we can update the board by shifting the candies down until there are no gaps. If the board is
not stable, we can repeat the process. The time complexity of this approach is O(n^2) for each pass, making it more efficient than the brute force
approach.
Algorithm:
While there are still candies that can be crushed:
Iterate over every cell in the board:
If the cell has not been visited and has a candy of the same type as its neighboring cells:
Perform a DFS to find all adjacent candies of the same type.
If the group is large enough to be crushed (three or more), mark all cells in the group for crushing.
If any cells were marked for crushing:
Crush all marked cells.
Shift candies down to fill gaps.
Return the stabilized board.
public int[][] CandyCrush(int[][] board) {
int rows = board.Length;
int cols = board[0].Length;
// repeatedly search for and crush candies until board becomes stable
while (true) {
bool hasCrush = false;
// mark candies to be crushed using DFS
bool[][] visited = new bool[rows][];
for (int i = 0; i < rows; i++) {
visited[i] = new bool[cols];
for (int j = 0; j < cols; j++) {
visited[i][j] = false;
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 0) continue;
int candy = board[i][j];
List<int[]> candies = new List<int[]>();
dfs(board, visited, i, j, candy, candies);
if (candies.Count >= 3) {
hasCrush = true;
foreach (int[] pos in candies) {
board[pos[0]][pos[1]] = 0; // mark candy for crushing
}
}
}
}
if (hasCrush) {
// crush marked candies and shift down
for (int j = 0; j < cols; j++) {
int bottom = rows - 1; // bottom non-empty cell
for (int i = rows - 1; i >= 0; i--) {
if (board[i][j] > 0) {
board[bottom--][j] = board[i][j]; // shift down candy
}
}
while (bottom >= 0) {
board[bottom--][j] = 0; // fill rest of column with zeros
}
}
} else {
// no more candies to crush, return board
return board;
}
}
}
private void dfs(int[][] board, bool[][] visited, int i, int j, int candy, List<int[]> candies) {
if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length || visited[i][j] || board[i][j] != candy) {
return;
}
visited[i][j] = true;
candies.Add(new int[] { i, j });
dfs(board, visited, i+1, j, candy, candies); // check down
dfs(board, visited, i-1, j, candy, candies); // check up
dfs(board, visited, i, j+1, candy, candies); // check right
dfs(board, visited, i, j-1, candy, candies); // check left
}
from typing import List
class Solution:
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
m, n = len(board), len(board[0])
found = True
while found:
found = False
# Find candies to crush horizontally
for i in range(m):
for j in range(n - 2):
val = abs(board[i][j])
if val != 0 and abs(board[i][j+1]) == val and abs(board[i][j+2]) == val:
board[i][j] = -val
board[i][j+1] = -val
board[i][j+2] = -val
found = True
# Find candies to crush vertically
for i in range(m - 2):
for j in range(n):
val = abs(board[i][j])
if val != 0 and abs(board[i+1][j]) == val and abs(board[i+2][j]) == val:
board[i][j] = -val
board[i+1][j] = -val
board[i+2][j] = -val
found = True
# Drop candies
for j in range(n):
row = m - 1
for i in range(m - 1, -1, -1):
if board[i][j] > 0:
board[row][j] = board[i][j]
row -= 1
while row >= 0:
board[row][j] = 0
row -= 1
return board
class Solution {
public int[][] candyCrush(int[][] board) {
int m = board.length;
int n = board[0].length;
boolean found = true;
while (found) {
found = false;
// Find candies to crush horizontally
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 2; j++) {
int val = Math.abs(board[i][j]);
if (val != 0 && Math.abs(board[i][j+1]) == val && Math.abs(board[i][j+2]) == val) {
board[i][j] = -val;
board[i][j+1] = -val;
board[i][j+2] = -val;
found = true;
}
}
}
// Find candies to crush vertically
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n; j++) {
int val = Math.abs(board[i][j]);
if (val != 0 && Math.abs(board[i+1][j]) == val && Math.abs(board[i+2][j]) == val) {
board[i][j] = -val;
board[i+1][j] = -val;
board[i+2][j] = -val;
found = true;
}
}
}
// Drop candies
for (int j = 0; j < n; j++) {
int row = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (board[i][j] > 0) {
board[row][j] = board[i][j];
row--;
}
}
while (row >= 0) {
board[row][j] = 0;
row--;
}
}
}
return board;
}
}
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:ve
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
int m = board.size();
int n = board[0].size();
bool found = true;
while (found) {
found = false;
// Find candies to crush horizontally
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 2; j++) {
int val = abs(board[i][j]);
if (val != 0 && abs(board[i][j+1]) == val && abs(board[i][j+2]) == val) {
board[i][j] = -val;
board[i][j+1] = -val;
board[i][j+2] = -val;
found = true;
}
}
}
// Find candies to crush vertically
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n; j++) {
int val = abs(board[i][j]);
if (val != 0 && abs(board[i+1][j]) == val && abs(board[i+2][j]) == val) {
board[i][j] = -val;
board[i+1][j] = -val;
board[i+2][j] = -val;
found = true;
}
}
}
// Drop candies
for (int j = 0; j < n; j++) {
int row = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (board[i][j] > 0) {
board[row--][j] = board[i][j];
}
}
while (row >= 0) {
board[row--][j] = 0;
}
}
}
return board;
}
};
Time complexity: O((mn)^2)
Space complexity: O(mn) (to store the visited nodes and recursion stack)
Breadth-First Search (BFS) Approach:
Another approach is to use BFS to identify groups of adjacent candies that have the same color, and then remove them. After removing the candies,
we can update the board by shifting the candies down until there are no gaps. If the board is not stable, we can repeat the process. The time
complexity of this approach is also O(n^2) for each pass.
Algorithm:
While there are still candies that can be crushed:
Iterate over every cell in the board:
If the cell has not been visited and has a candy of the same type as its neighboring cells:
Perform a BFS to find all adjacent candies of the same type.
If the group is large enough to be crushed (three or more), mark all cells in the group for crushing.
If any cells were marked for crushing:
Crush all marked cells.
Shift candies down to fill gaps.
Return the stabilized board.
public class Solution {
public int[][] CandyCrush(int[][] board) {
int m = board.Length;
int n = board[0].Length;
while (true) {
bool crush = false;
bool[,] visited = new bool[m,n];
// Perform BFS on each candy
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 0 || visited[i,j]) {
continue;
}
List<(int,int)> candies = new List<(int,int)>();
candies.Add((i,j));
// Find all adjacent candies of the same type
for (int k = 0; k < candies.Count; k++) {
int x = candies[k].Item1;
int y = candies[k].Item2;
if (x > 0 && board[x-1][y] == board[x][y]) {
candies.Add((x-1,y));
}
if (x < m-1 && board[x+1][y] == board[x][y]) {
candies.Add((x+1,y));
}
if (y > 0 && board[x][y-1] == board[x][y]) {
candies.Add((x,y-1));
}
if (y < n-1 && board[x][y+1] == board[x][y]) {
candies.Add((x,y+1));
}
}
// Crush candies if there are more than three
if (candies.Count >= 3) {
crush = true;
foreach (var candy in candies) {
board[candy.Item1][candy.Item2] = 0;
}
}
// Mark visited candies
foreach (var candy in candies) {
visited[candy.Item1,candy.Item2] = true;
}
}
}
// Drop candies
for (int j = 0; j < n; j++) {
int bottom = m-1;
for (int i = m-1; i >= 0; i--) {
if (board[i][j] != 0) {
board[bottom][j] = board[i][j];
bottom--;
}
}
while (bottom >= 0) {
board[bottom][j] = 0;
bottom--;
}
}
// Exit loop if no candies were crushed
if (!crush) {
break;
}
}
return board;
}
}
from typing import List
def candyCrush(board: List[List[int]]) -> List[List[int]]:
def gravity(board: List[List[int]]) -> List[List[int]]:
# shift candies down starting from the bottom row
for j in range(len(board[0])):
idx = len(board) - 1
for i in range(len(board) - 1, -1, -1):
if board[i][j] != 0:
board[idx][j] = board[i][j]
idx -= 1
while idx >= 0:
board[idx][j] = 0
idx -= 1
return board
def bfs(board: List[List[int]]) -> List[List[int]]:
queue = []
queue.append(board)
while queue:
curr_board = queue.pop(0)
# mark all the candies that needs to be crushed
crush_candies = set()
for i in range(len(curr_board)):
for j in range(len(curr_board[0])):
if curr_board[i][j] == 0:
continue
if i > 1 and curr_board[i][j] == curr_board[i-1][j] == curr_board[i-2][j]:
crush_candies.add((i,j))
crush_candies.add((i-1,j))
crush_candies.add((i-2,j))
if j > 1 and curr_board[i][j] == curr_board[i][j-1] == curr_board[i][j-2]:
crush_candies.add((i,j))
crush_candies.add((i,j-1))
crush_candies.add((i,j-2))
# crush the marked candies
if len(crush_candies) == 0:
return curr_board
for i, j in crush_candies:
curr_board[i][j] = 0
# apply gravity and add the new board state to the queue
new_board = gravity(curr_board)
queue.append(new_board)
return board
return bfs(board)
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int[][] candyCrush(int[][] board) {
int m = board.length;
int n = board[0].length;
while (true) {
boolean toCrush = false;
boolean[][] visited = new boolean[m][n];
// Step 1: Identify candies to crush using BFS
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 0 || visited[i][j]) {
// skip if cell is empty or already visited
continue;
}
int candy = board[i][j];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
visited[i][j] = true;
int count = 1;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int row = curr[0];
int col = curr[1];
// Check horizontally
if (col < n - 1 && board[row][col + 1] == candy && !visited[row][col + 1]) {
queue.offer(new int[]{row, col + 1});
visited[row][col + 1] = true;
count++;
}
if (col > 0 && board[row][col - 1] == candy && !visited[row][col - 1]) {
queue.offer(new int[]{row, col - 1});
visited[row][col - 1] = true;
count++;
}
// Check vertically
if (row < m - 1 && board[row + 1][col] == candy && !visited[row + 1][col]) {
queue.offer(new int[]{row + 1, col});
visited[row + 1][col] = true;
count++;
}
if (row > 0 && board[row - 1][col] == candy && !visited[row - 1][col]) {
queue.offer(new int[]{row - 1, col});
visited[row - 1][col] = true;
count++;
}
}
// If we found 3 or more candies to crush, mark them as to be crushed
if (count >= 3) {
toCrush = true;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (visited[r][c]) {
board[r][c] = 0;
}
}
}
}
}
}
// Step 2: Crush candies by shifting down non-zero values and replacing top row with 0
if (!toCrush) {
break;
}
for (int j = 0; j < n; j++) {
int insertIdx = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (board[i][j] != 0) {
board[insertIdx][j] = board[i][j];
insertIdx--;
}
}
while (insertIdx >= 0) {
board[insertIdx][j] = 0;
insertIdx--;
}
}
}
return board;
}
}
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
int m = board.size();
int n = board[0].size();
bool found = true;
while (found) {
found = false;
// create a queue to store the coordinates of candies that need to be crushed
queue<pair<int, int>> q;
// check for horizontal candies to be crushed
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 2; j++) {
if (board[i][j] != 0 && abs(board[i][j]) == abs(board[i][j+1]) && abs(board[i][j]) == abs(board[i][j+2])) {
q.push({i, j});
q.push({i, j+1});
q.push({i, j+2});
found = true;
}
}
}
// check for vertical candies to be crushed
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] != 0 && abs(board[i][j]) == abs(board[i+1][j]) && abs(board[i][j]) == abs(board[i+2][j])) {
q.push({i, j});
q.push({i+1, j});
q.push({i+2, j});
found = true;
}
}
}
// crush the candies in the queue by setting their values to 0
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
board[i][j] = 0;
}
// drop the candies that are still present on the board
for (int j = 0; j < n; j++) {
int k = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (board[i][j] != 0) {
board[k--][j] = board[i][j];
}
}
while (k >= 0) {
board[k--][j] = 0;
}
}
}
return board;
}
Time complexity: O((mn)^2)
Space complexity: O(mn) (to store the queue and visited nodes)
Simulation Approach:
Another approach is to simulate the game by applying the rules of the game repeatedly until the board becomes stable. We can represent the board
as a matrix, and then simulate the game by applying the rules to each cell in the matrix. This approach is more complicated than the other
approaches, but it has a time complexity of O(n^2) for each pass, making it more efficient than the brute force approach.
Algorithm:
While there are still candies that can be crushed:
Create a copy of the board.
Iterate over every cell in the copy:
If the cell has a candy of the same type as its neighboring cells, mark it for crushing.
If any cells were marked for crushing:
Crush all marked cells in the original board.
Shift candies down to fill gaps.
Return the stabilized board.
public int[][] CandyCrush(int[][] board) {
int rows = board.Length;
int cols = board[0].Length;
bool isStable = false;
while (!isStable) {
isStable = true;
// Step 1: Find all candies to crush
List<(int, int)> candiesToCrush = new List<(int, int)>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == 0) {
continue;
}
if (c < cols - 2 && board[r][c] == board[r][c+1] && board[r][c] == board[r][c+2]) {
candiesToCrush.Add((r, c));
candiesToCrush.Add((r, c+1));
candiesToCrush.Add((r, c+2));
}
if (r < rows - 2 && board[r][c] == board[r+1][c] && board[r][c] == board[r+2][c]) {
candiesToCrush.Add((r, c));
candiesToCrush.Add((r+1, c));
candiesToCrush.Add((r+2, c));
}
}
}
// Step 2: Crush all candies in the list
foreach ((int r, int c) in candiesToCrush) {
board[r][c] = 0;
}
// Step 3: Drop candies
for (int c = 0; c < cols; c++) {
int idx = rows - 1;
for (int r = rows - 1; r >= 0; r--) {
if (board[r][c] != 0) {
int temp = board[r][c];
board[r][c] = board[idx][c];
board[idx][c] = temp;
idx--;
}
}
}
// Step 4: Check if the board is stable
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == 0) {
continue;
}
if (c < cols - 2 && board[r][c] == board[r][c+1] && board[r][c] == board[r][c+2]) {
isStable = false;
}
if (r < rows - 2 && board[r][c] == board[r+1][c] && board[r][c] == board[r+2][c]) {
isStable = false;
}
}
}
}
return board;
}
def candy_crush(board):
"""
Simulate crushing candies on the given board until it becomes stable
"""
n_rows, n_cols = len(board), len(board[0])
def mark_candies_to_crush():
"""
Mark candies that need to be crushed in the next step
"""
crushed = set()
for i in range(n_rows):
for j in range(n_cols):
if board[i][j] == 0:
continue
# check horizontally
if j < n_cols - 2 and board[i][j] == board[i][j+1] == board[i][j+2]:
crushed |= {(i, j), (i, j+1), (i, j+2)}
# check vertically
if i < n_rows - 2 and board[i][j] == board[i+1][j] == board[i+2][j]:
crushed |= {(i, j), (i+1, j), (i+2, j)}
return crushed
def crush_candies(crushed):
"""
Crush the marked candies on the board
"""
for i, j in crushed:
board[i][j] = 0
def drop_candies():
"""
Let the candies above the empty cells drop down
"""
for j in range(n_cols):
k = n_rows - 1
for i in range(n_rows-1, -1, -1):
if board[i][j] != 0:
board[k][j] = board[i][j]
k -= 1
for i in range(k, -1, -1):
board[i][j] = 0
while True:
# mark candies to crush in this step
candies_to_crush = mark_candies_to_crush()
if not candies_to_crush:
# board is stable, return it
return board
# crush marked candies
crush_candies(candies_to_crush)
# let candies above empty cells drop down
drop_candies()
public int[][] candyCrush(int[][] board) {
int n = board.length;
int m = board[0].length;
boolean stable = false;
while (!stable) {
stable = true;
boolean[][] toCrush = new boolean[n][m];
// Find candies to crush horizontally
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 2; j++) {
if (board[i][j] != 0 && board[i][j] == board[i][j + 1] && board[i][j] == board[i][j + 2]) {
toCrush[i][j] = true;
toCrush[i][j + 1] = true;
toCrush[i][j + 2] = true;
stable = false;
}
}
}
// Find candies to crush vertically
for (int j = 0; j < m; j++) {
for (int i = 0; i < n - 2; i++) {
if (board[i][j] != 0 && board[i][j] == board[i + 1][j] && board[i][j] == board[i + 2][j]) {
toCrush[i][j] = true;
toCrush[i + 1][j] = true;
toCrush[i + 2][j] = true;
stable = false;
}
}
}
// Crush candies and drop candies
for (int j = 0; j < m; j++) {
int k = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (!toCrush[i][j]) {
board[k][j] = board[i][j];
k--;
}
}
for (int i = k; i >= 0; i--) {
board[i][j] = 0;
}
}
}
return board;
}
C#:
This code uses a while loop to simulate the game until the board becomes stable. Inside the loop, it performs the following steps:
Find all candies that need to be crushed: This is done by iterating over the board and checking if three or more candies of the same type are
adjacent vertically or horizontally.
Crush all candies in the list: This is done by setting the value of the corresponding cells to 0.
Drop candies: This is done by iterating over each column and shifting all non-zero values to the bottom of the column.
Check if the board is stable: This is done by iterating over the board again and checking if
Python:
The candy_crush function takes a 2D integer list board as input and returns the stabilized board after crushing candies.
It consists of three nested helper functions:
mark_candies_to_crush: This function marks the candies that need to be crushed in the next step. It scans the board row by row, and
column by column, and checks if there are three or more candies of the same type that are adjacent horizontally or vertically. If such a group
of candies is found, the function marks all the candies in the group to be crushed.
crush_candies: This function crushes the marked candies by setting their value to 0.
drop_candies: This function lets the candies above the empty cells drop down by shifting each non-empty cell downwards until it
reaches an empty cell or the bottom of the board.
The main loop of the candy_crush function repeatedly performs the three steps until the board becomes stable:
Mark the candies to crush in this step
Crush the marked candies
Let candies above empty cells drop down
If at any step, no candies are marked for crushing, it means that the board is stable, and the function returns the stabilized board.
Java:
This code implements the simulation approach in Java. It first initializes the board dimensions and sets a
stable flag to false, indicating that the board is not yet stable. It then enters a while loop that continues until the board becomes
stable.
In each iteration of the while loop, the code initializes a
toCrush boolean array that will be used to mark which candies need to be crushed. It then iterates over each row of the board and
checks if there are any sets of three consecutive candies of the same type that need to be crushed horizontally. If so, it marks the candies in
the toCrush array and sets the stable flag to false. It then does the same for each column of the board to check for
vertical sets of three.
After marking the candies to crush, the code iterates over each column of the board and moves the candies down to fill in any empty spaces left by
the crushed candies. It starts from the bottom of the column and moves upwards, copying non-crushed candies to the bottom of the column, and
setting any empty spaces at the top to 0.
Finally, the code returns the modified board.
Time complexity: O((mn)^2)
Space complexity: O(1) (no extra space used)
As we can see, the Brute Force approach has the worst time complexity among the four approaches, making it impractical for larger board sizes.
The DFS and BFS approaches have a better time complexity but require additional space to store the visited nodes and the recursion/queue stack.
The Simulation approach, on the other hand, has a similar time complexity to the DFS and BFS approaches but uses constant space.
Overall, if the board size is small and memory is not a concern, the DFS or BFS approach can be used. However, for larger board sizes or limited
memory, the Simulation approach is the most practical.
