723. Candy Crush

MediumArrayTwo PointersMatrixSimulation
Leetcode Link

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.

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.

💪
Level Up Your
Algo Skills

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.

Python Solution

1from typing import List
2
3class Solution:
4    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
5        # Dimensions of the board
6        num_rows, num_cols = len(board), len(board[0])
7      
8        # Flag to indicate if we should continue crushing candies
9        should_crush = True
10      
11        # Keep crushing candies until no more moves can be made
12        while should_crush:
13            should_crush = False  # Reset the flag for each iteration
14          
15            # Mark the candies to be crushed horizontally
16            for row in range(num_rows):
17                for col in range(num_cols - 2):
18                    candy_value = abs(board[row][col])
19                    # Check if three consecutive candies have the same value
20                    if candy_value != 0 and candy_value == abs(board[row][col + 1]) == abs(board[row][col + 2]):
21                        should_crush = True  # We will need another pass after crushing
22                        # Mark the candies for crushing by negating their value
23                        board[row][col] = board[row][col + 1] = board[row][col + 2] = -candy_value
24                      
25            # Mark the candies to be crushed vertically
26            for col in range(num_cols):
27                for row in range(num_rows - 2):
28                    candy_value = abs(board[row][col])
29                    # Check if three consecutive candies vertically have the same value
30                    if candy_value != 0 and candy_value == abs(board[row + 1][col]) == abs(board[row + 2][col]):
31                        should_crush = True  # We will need another pass after crushing
32                        # Mark the candies for crushing
33                        board[row][col] = board[row + 1][col] = board[row + 2][col] = -candy_value
34                      
35            # Drop the candies to fill the empty spaces caused by crushing
36            if should_crush:
37                for col in range(num_cols):
38                    # Pointer to where the next non-crushed candy will fall
39                    write_row = num_rows - 1
40                    for row in range(num_rows - 1, -1, -1):
41                        # If the candy is not marked for crushing, bring it down
42                        if board[row][col] > 0:
43                            board[write_row][col] = board[row][col]
44                            write_row -= 1
45                    # Fill the remaining spaces at the top with zeros
46                    while write_row >= 0:
47                        board[write_row][col] = 0
48                        write_row -= 1
49                      
50        # Return the modified board after all possible crushes are completed
51        return board
52

Java Solution

1class Solution {
2    public int[][] candyCrush(int[][] board) {
3        int rows = board.length;
4        int cols = board[0].length;
5        boolean shouldContinue = true;
6
7        // Loop until no more candies can be crushed
8        while (shouldContinue) {
9            shouldContinue = false;
10
11            // Mark candies that need to be crushed in the horizontal direction
12            for (int i = 0; i < rows; ++i) {
13                for (int j = 0; j < cols - 2; ++j) {
14                    int value = Math.abs(board[i][j]);
15                    if (value != 0 && value == Math.abs(board[i][j + 1]) && value == Math.abs(board[i][j + 2])) {
16                        shouldContinue = true;
17                        board[i][j] = board[i][j + 1] = board[i][j + 2] = -value;
18                    }
19                }
20            }
21
22            // Mark candies that need to be crushed in the vertical direction
23            for (int j = 0; j < cols; ++j) {
24                for (int i = 0; i < rows - 2; ++i) {
25                    int value = Math.abs(board[i][j]);
26                    if (value != 0 && value == Math.abs(board[i + 1][j]) && value == Math.abs(board[i + 2][j])) {
27                        shouldContinue = true;
28                        board[i][j] = board[i + 1][j] = board[i + 2][j] = -value;
29                    }
30                }
31            }
32          
33            // Crush the candies and let new ones fall down
34            if (shouldContinue) {
35                for (int j = 0; j < cols; ++j) {
36                    // Start from bottom of the board
37                    int writeIndex = rows - 1;
38                    for (int i = rows - 1; i >= 0; --i) {
39                        // If this candy is not marked to be crushed, bring it down
40                        if (board[i][j] > 0) {
41                            board[writeIndex][j] = board[i][j];
42                            writeIndex--;
43                        }
44                    }
45                    // Fill the remaining spaces with 0s to indicate empty spaces
46                    while (writeIndex > -1) {
47                        board[writeIndex][j] = 0;
48                        writeIndex--;
49                    }
50                }
51            }
52        }
53
54        return board;
55    }
56}
57

C++ Solution

1class Solution {
2public:
3    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
4        int numRows = board.size(), numCols = board[0].size();
5        bool foundCrushableCandies = true;
6
7        // Continue the process as long as we find crushable candies
8        while (foundCrushableCandies) {
9            foundCrushableCandies = false;
10
11            // Mark the crushable candies in rows by making their values negative
12            for (int row = 0; row < numRows; ++row) {
13                for (int col = 0; col < numCols - 2; ++col) {
14                    int candyValue = abs(board[row][col]);
15                    if (candyValue != 0 &&
16                        candyValue == abs(board[row][col + 1]) &&
17                        candyValue == abs(board[row][col + 2])) {
18                        foundCrushableCandies = true;
19                        board[row][col] = board[row][col + 1] = board[row][col + 2] = -candyValue;
20                    }
21                }
22            }
23
24            // Mark the crushable candies in columns by making their values negative
25            for (int col = 0; col < numCols; ++col) {
26                for (int row = 0; row < numRows - 2; ++row) {
27                    int candyValue = abs(board[row][col]);
28                    if (candyValue != 0 &&
29                        candyValue == abs(board[row + 1][col]) &&
30                        candyValue == abs(board[row + 2][col])) {
31                        foundCrushableCandies = true;
32                        board[row][col] = board[row + 1][col] = board[row + 2][col] = -candyValue;
33                    }
34                }
35            }
36
37            // Crush the marked candies and let the candies fall down to fill the empty spaces
38            if (foundCrushableCandies) {
39                for (int col = 0; col < numCols; ++col) {
40                    int fillPosition = numRows - 1;
41                  
42                    // Move non-crushable candies down
43                    for (int row = numRows - 1; row >= 0; --row) {
44                        if (board[row][col] > 0) {
45                            board[fillPosition][col] = board[row][col];
46                            fillPosition--;
47                        }
48                    }
49                  
50                    // Fill the remaining spaces with 0s
51                    while (fillPosition >= 0) {
52                        board[fillPosition][col] = 0;
53                        fillPosition--;
54                    }
55                }
56            }
57        }
58
59        return board;
60    }
61};
62

Typescript Solution

1// Define the matrix type
2type Matrix = number[][];
3
4// Find and crush the crushable candies, then return the updated board
5function candyCrush(board: Matrix): Matrix {
6    let numRows = board.length;
7    let numCols = board[0].length;
8    let foundCrushableCandies = true;
9
10    // Continue the process as long as we find crushable candies
11    while (foundCrushableCandies) {
12        foundCrushableCandies = false;
13
14        // Mark the crushable candies in rows by making their values negative
15        for (let row = 0; row < numRows; ++row) {
16            for (let col = 0; col < numCols - 2; ++col) {
17                let candyValue = Math.abs(board[row][col]);
18                if (candyValue !== 0 &&
19                    candyValue === Math.abs(board[row][col + 1]) &&
20                    candyValue === Math.abs(board[row][col + 2])) {
21                    foundCrushableCandies = true;
22                    board[row][col] = board[row][col + 1] = board[row][col + 2] = -candyValue;
23                }
24            }
25        }
26
27        // Mark the crushable candies in columns by making their values negative
28        for (let col = 0; col < numCols; ++col) {
29            for (let row = 0; row < numRows - 2; ++row) {
30                let candyValue = Math.abs(board[row][col]);
31                if (candyValue !== 0 &&
32                    candyValue === Math.abs(board[row + 1][col]) &&
33                    candyValue === Math.abs(board[row + 2][col])) {
34                    foundCrushableCandies = true;
35                    board[row][col] = board[row + 1][col] = board[row + 2][col] = -candyValue;
36                }
37            }
38        }
39
40        // Crush the marked candies and let the candies fall down to fill the empty spaces
41        if (foundCrushableCandies) {
42            for (let col = 0; col < numCols; ++col) {
43                let fillPosition = numRows - 1;
44
45                // Move non-crushable candies down
46                for (let row = numRows - 1; row >= 0; --row) {
47                    if (board[row][col] > 0) {
48                        board[fillPosition][col] = board[row][col];
49                        fillPosition--;
50                    }
51                }
52
53                // Fill the remaining spaces with 0s
54                for (let fill = fillPosition; fill >= 0; fill--) {
55                    board[fill][col] = 0;
56                }
57            }
58        }
59    }
60
61    return board;
62}
63

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫