# Candy Crush

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:

1. 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.
2. 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.
3. After the above steps, there may exist more candies that can be crushed. If so, repeat the above steps.
4. 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.

## Examples

```Input: 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]]
Output: [[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]]```
```Input: 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]]
Output: [[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]]```

## Clarifying Questions

1. Can you provide an example input and output for this problem?
2. Can we assume that the board will always be rectangular (i.e., m x n dimensions)?
3. What should be returned if the initial board is already stable?
4. Are there any restrictions on the time complexity or space complexity of the solution?
5. 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.

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.

Time complexity: O((mn)^2)

Space complexity: O(mn) (to store the visited nodes and recursion stack)

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.

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.

#### C#:

This code uses a while loop to simulate the game until the board becomes stable. Inside the loop, it performs the following steps:

1. 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.

2. Crush all candies in the list: This is done by setting the value of the corresponding cells to 0.

3. Drop candies: This is done by iterating over each column and shifting all non-zero values to the bottom of the column.

4. 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:

1. Mark the candies to crush in this step
2. Crush the marked candies
3. 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.

Share: