723. Candy Crush

Problem Description

This problem requires you to simulate the game "Candy Crush". Given a 2D grid representing a candy board of size m x n, where each cell contains an integer that represents a different type of candy, your task is to implement an algorithm that performs a series of crushing actions according to the game's rules.

The crushing rules are as follows:

• When three or more candies of the same type are adjacent either vertically or horizontally, they all get crushed at once, and their positions are set to zero, indicating an empty cell.
• Once candies are crushed, gravity comes into play. Any candies above the empty cells will fall down to fill the empty spaces.
• New candies do not enter the board from the top. Only existing candies drop down.
• The crushing and dropping process continues until no more crushing can occur—i.e., no groups of three or more adjacent candies of the same type are left.

The goal is to keep applying these rules until the board reaches a stable state with no more possible crushes. The final stable board should be returned.

Intuition

The solution is iterative and simulates the game's mechanics step by step. Here's how the intuition unfolds:

• Initial Check for Crushes: Start by scanning the board to find any rows or columns of three or more candies that can be crushed. We keep a boolean flag, run, tracking if we performed a crushing operation during the current iteration. This flag indicates whether we need to continue processing the board.

• Marking Candies for Crushing: When we find three or more candies in a row or column that match, we mark them by negating their value. It allows us to distinguish between candies that will be crushed and the rest of the board.

• Crushing Candies: Once we are done checking the entire board and have marked all candies to be crushed, we perform the actual crushing by replacing the marked candies (negative numbers) with zeros.

• Implementing Gravity: After crushing, simulate gravity by letting the uncrushed candies (positive numbers) fall down to fill any gaps. This is done by moving candies down within each column, starting from the bottom up.

• Repeating the Process: Once we've completed a crush and gravity step, we need to check if more crushes can be made because the falling candies might create new sequences of three or more matching candies. We repeat the process as long as we keep crushing candies in each iteration. The run flag helps us to determine this; if set to True, at least one crushing occurred, so we need another pass.

• Stable Board: Finally, when no more crushes occur in a whole pass (i.e., run is False), the board is stable, and we return it.

By iterating through these steps, the given algorithm ensures that all possible crushes are made and that the board reaches a stable state according to Candy Crush rules.

Learn more about Two Pointers patterns.

Solution Approach

The implementation of the solution involves several important steps, each taking advantage of basic algorithms and data structures.

1. Marking Candies to Crush: We loop through the entire board, searching for sequences of three or more similar candies either horizontally or vertically. We use two nested loops for this - one for rows and one for columns. When we find such a sequence, we mark the candies by negating their values using abs(board[i][j]) to indicate these will be crushed. The use of negation allows us to retain the candy type information, which is important to check for subsequent crushes in later iterations.

2. Horizontal Crushing: This part checks for three or more adjacent candies horizontally. The following snippet from the code performs horizontal checks and marks the candies:

   1for i in range(m):
   2    for j in range(n - 2):
   3        if (board[i][j] != 0
   4            and abs(board[i][j]) == abs(board[i][j + 1])
   5            and abs(board[i][j]) == abs(board[i][j + 2])):
   6            run = True
   7            board[i][j] = board[i][j + 1] = board[i][j + 2] = -abs(board[i][j])

3. Vertical Crushing: Similar to the horizontal checks, we perform vertical checks as well, identifying candies that should be crushed and marking them as negative numbers. Code snippet for the vertical check:

   1for j in range(n):
   2    for i in range(m - 2):
   3        if (board[i][j] != 0
   4            and abs(board[i][j]) == abs(board[i + 1][j])
   5            and abs(board[i][j]) == abs(board[i + 2][j])):
   6            run = True
   7            board[i][j] = board[i + 1][j] = board[i + 2][j] = -abs(board[i][j])

4. Candies Falling (Gravity): Once all possible candies are marked, we need to let all the unmarked (positive) candies fall down. We iterate through each column starting from the bottom row and move unmarked candies down to the ‘curr’ position, which represents the next available uncrushed position from the bottom. The code for simulating gravity is as follows:

   1for j in range(n):
   2    curr = m - 1
   3    for i in range(m - 1, -1, -1):
   4        if board[i][j] > 0:
   5            board[curr][j] = board[i][j]
   6            curr -= 1
   7    while curr > -1:
   8        board[curr][j] = 0
   9        curr -= 1

5. Repeating Until Stable: The outer while run: loop allows us to repeat this process until no further candies can be crushed. The run flag is set to True whenever a crush happens, prompting another iteration. When an iteration completes with no candies crushed (run is False), the board is stable, and the loop will terminate.

6. Returning the Result: After the loop exits, we return the stabilized board. There are no extra data structures used outside of the input board, which is mutated in place to save space, and simple variables for iteration control.

By iterating over the marked candies and applying gravity as long as there are candies to crush, the algorithm ensures an accurate portrayal of the Candy Crush mechanism.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using a simple 3x3 grid to demonstrate the Candy Crush algorithm.

Suppose our initial 3x3 grid is as follows:

11 1 1
22 2 3
33 3 2

Following the solution approach:

1. Marking Candies to Crush: First, we look for horizontal and vertical sequences of three or more similar candies to mark for crushing. We see that the top row has three 1s horizontally.

   After marking, our grid looks like this:

   1-1 -1 -1
   22  2  3
   33  3  2

   There are no vertical sequences to mark, so we continue to the next step.

2. Horizontal and Vertical Crushing: Since we've already marked the candies in step 1, we now set those positions to zero, simulating the crush.

   Our grid now looks like this:

   10 0 0
   22 2 3
   33 3 2

3. Candies Falling (Gravity): We apply gravity, allowing the candies to fall down to fill the empty spaces. Starting from the bottom of each column, we move positive numbers down.

   After gravity, our grid becomes:

   10 0 0
   20 0 0
   32 2 3

   Now we have uncrushed candies at the bottom with zeros representing the empty cells above them.

4. Repeating Until Stable: We need to check again if any new sequences of three or more similar candies have formed due to gravity. Since no such sequences exist, no further action is required, and the run flag remains False.

5. Returning the Result: With no further crushes possible, and the board in a stable state, this is the final board state:

   10 0 0
   20 0 0
   32 2 3

And this is the state we return as our answer, illustrating a simple run-through of the Candy Crush algorithm.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by the nested loops and the operations performed within them. Let's analyze it step by step.

1. The outer while loop that repeats until no more candies can be crushed (run = False) will run until the board stabilizes, which relates to the dimensions of the board. In the worst case, this might be O(m * n) because each candy might need to fall all the way down the board in the most extreme case.

2. Inside the while loop, there are two sets of nested for loops: one for checking rows and one for checking columns for crushable candies. Both of these sets involve iterating over all elements on the board once, giving us a O(m * n) for each full scan.

3. Crushing candies and making them negative take O(1) time each, but since it's inside the nested loops, it doesn't add more than a constant factor to the overall complexity of scanning the board.

4. The final part within the while loop is another nested loop that handles gravity, making candies fall down. This, again, requires going over each column and, in the worst case, moving each candy down to the bottom, which takes O(m) for each column. Multiplying by n columns gives us O(m * n).

Combining these, in the worst case, the while loop may run m * n times due to the possibility of each iteration only crushing one candy and making others fall one place. This is a pessimistic estimate, but it serves as an upper boundary. Thus, the time complexity of the nested loops, taken together, results in O((m * n) * (m * n)) or O((m * n)^2).

Space Complexity

The space complexity of the code is:

1. O(1) for the variables m, n, run, curr, and i, j inside loops, as they do not depend on the size of the board and use a constant amount of space.

2. The input board is modified in-place and no additional data structures of significant size are created or used in the process, meaning we do not use additional space proportional to the size of the input.

Hence, the space complexity of the algorithm is O(1).

Note: While the actual number of iterations needed to stabilize the board might be much less than m * n, we are considering the worst-case time complexity here for completeness.

Learn more about how to find time and space complexity quickly using problem constraints.