Candy Crush

Medium

Candy Crush

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the candy values? Can I assume they are integers, or could they be characters representing different candy types?
What are the dimensions of the game board (number of rows and columns)? Is the board guaranteed to be rectangular?
When 'crushing' candies, if a candy is part of both a horizontal and a vertical crush, should it be crushed in both directions simultaneously?
After crushing, how should the board be updated? Should candies fall down to fill the empty spaces, and if so, how is gravity applied (e.g., from top to bottom)?
If there are multiple possible crush moves, does the order in which I apply them matter, or can I choose any valid crushing sequence?

Brute Force Solution

Approach

The brute force way to solve Candy Crush is to repeatedly scan the board for any groups of three or more candies in a row or column. When we find a group, we crush it and let the remaining candies fall down to fill the gaps. We keep doing this until there are no more groups to crush.

Here's how the algorithm would work step-by-step:

Look at every single spot on the game board.
For each spot, check if there are at least two identical candies next to it to form a line of three or more (horizontally or vertically).
If a line of three or more is found, mark those candies for removal.
Once you've checked the entire board, remove all the marked candies at once, making those spaces empty.
Let the candies above the empty spaces fall down to fill them.
Fill any remaining empty spaces at the top with new, random candies.
Repeat this whole process from the beginning until there are no more lines of three or more candies anywhere on the board.

Code Implementation

def candy_crush_brute_force(board):
    rows = len(board)
    columns = len(board[0])

    def crush_board(board):
        rows_to_crush = set()
        columns_to_crush = set()

        # Find horizontal matches
        for row_index in range(rows):
            for column_index in range(columns - 2):
                if board[row_index][column_index] != 0 and \
                   board[row_index][column_index] == board[row_index][column_index + 1] and \
                   board[row_index][column_index] == board[row_index][column_index + 2]:
                    rows_to_crush.add((row_index, column_index))
                    rows_to_crush.add((row_index, column_index + 1))
                    rows_to_crush.add((row_index, column_index + 2))

        # Find vertical matches
        for row_index in range(rows - 2):
            for column_index in range(columns):
                if board[row_index][column_index] != 0 and \
                   board[row_index][column_index] == board[row_index + 1][column_index] and \
                   board[row_index][column_index] == board[row_index + 2][column_index]:
                    columns_to_crush.add((row_index, column_index))
                    columns_to_crush.add((row_index + 1, column_index))
                    columns_to_crush.add((row_index + 2, column_index))

        # Crush candies
        if not rows_to_crush and not columns_to_crush:
            return False

        for row_index, column_index in rows_to_crush:
            board[row_index][column_index] = 0

        for row_index, column_index in columns_to_crush:
            board[row_index][column_index] = 0

        # Apply gravity
        for column_index in range(columns):
            bottom = rows - 1
            for row_index in range(rows - 1, -1, -1):
                if board[row_index][column_index] != 0:
                    board[bottom][column_index] = board[row_index][column_index]
                    bottom -= 1

            # Fill top with zeros
            for row_index in range(bottom, -1, -1):
                board[row_index][column_index] = 0

        return True

    # Keep crushing until no more crushes are possible
    while crush_board(board):
        continue

    return board

Big(O) Analysis

Time Complexity

O(m*n*max(m,n)) – Let m be the number of rows and n be the number of columns. The algorithm repeatedly scans the m*n board to identify horizontal and vertical lines of 3 or more candies. In the worst case, each crush operation may only remove a small number of candies, so we might need to repeat this process multiple times. Identifying and marking candies for removal takes O(m*n) time. After marking, we need to drop the candies, which in the worst case, requires traversing the height or width of the board, taking O(max(m,n)) time for each of the m*n cells. Therefore the entire process must run multiple times so the total time complexity is O(m*n*max(m,n)).

Space Complexity

O(M * N) – The provided algorithm uses a data structure (e.g., a boolean matrix) to mark candies for removal. The size of this data structure is directly proportional to the dimensions of the game board, which we can denote as M rows and N columns. Therefore, the space required to store these markings is M * N. No other significant auxiliary space is used. Thus, the space complexity is O(M * N), where M and N are the dimensions of the candy crush board.

Optimal Solution

Approach

The most efficient way to 'Candy Crush' is to repeatedly identify and remove matching groups until no more matches exist. This involves scanning the board and eliminating all matches in each pass before moving to the next iteration.

Here's how the algorithm would work step-by-step:

Continuously look across the entire game board to find any sequences of three or more candies that are the same.
When you find a matching sequence, remove those candies from the board.
After removing the candies, let the candies above fall down to fill the empty spaces.
Once the candies have fallen, check again for any new matching sequences that may have been created by the falling candies.
Keep repeating the process of finding matches, removing them, and letting candies fall until there are no more matches left on the board.

Code Implementation

def candy_crush(board):
    rows = len(board)
    columns = len(board[0])

    def mark_horizontal_matches():
        for row_index in range(rows):
            for column_index in range(columns - 2):
                if board[row_index][column_index] != 0 and \
                   board[row_index][column_index] == board[row_index][column_index + 1] and \
                   board[row_index][column_index] == board[row_index][column_index + 2]:
                    # Mark horizontal matches as negative
                    board[row_index][column_index] = -abs(board[row_index][column_index])
                    board[row_index][column_index + 1] = -abs(board[row_index][column_index + 1])
                    board[row_index][column_index + 2] = -abs(board[row_index][column_index + 2])

    def mark_vertical_matches():
        for row_index in range(rows - 2):
            for column_index in range(columns):
                if board[row_index][column_index] != 0 and \
                   board[row_index][column_index] == board[row_index + 1][column_index] and \
                   board[row_index][column_index] == board[row_index + 2][column_index]:
                    # Mark vertical matches as negative
                    board[row_index][column_index] = -abs(board[row_index][column_index])
                    board[row_index + 1][column_index] = -abs(board[row_index + 1][column_index])
                    board[row_index + 2][column_index] = -abs(board[row_index + 2][column_index])

    def drop_candies():
        for column_index in range(columns):
            bottom = rows - 1
            for row_index in range(rows - 1, -1, -1):
                if board[row_index][column_index] > 0:
                    board[bottom][column_index] = board[row_index][column_index]
                    bottom -= 1

            # Fill the remaining top cells with 0
            for row_index in range(bottom, -1, -1):
                board[row_index][column_index] = 0

    while True:
        mark_horizontal_matches()
        mark_vertical_matches()

        has_match = False
        for row_index in range(rows):
            for column_index in range(columns):
                if board[row_index][column_index] < 0:
                    has_match = True
                    break
            if has_match:
                break

        if not has_match:
            break

        # Remove matches by setting them to 0
        for row_index in range(rows):
            for column_index in range(columns):
                if board[row_index][column_index] < 0:
                    board[row_index][column_index] = 0

        # Drop candies to fill empty spaces
        drop_candies()

    return board

Big(O) Analysis

Time Complexity

O(m*n*(m+n)) – The algorithm repeatedly scans the m x n board to find candy matches. Finding matches in each row or column takes O(m) or O(n) time, respectively. Since we check both rows and columns, a single pass for finding and removing all matches takes O(m*n) time. After removing matches, we need to drop candies, which in the worst case involves shifting all candies above the cleared ones and this can take O(m+n) time. We repeat this process until no more matches are found. The number of iterations depends on the board state and is hard to pinpoint but in the worst case, it is possible to have O(m*n) iterations, so the total time complexity becomes O(m*n*(m+n)).

Space Complexity

O(1) – The algorithm primarily modifies the input board in place. The matching sequences are identified and removed directly on the board, and the falling candies operation also happens in place. There are no auxiliary data structures used that scale with the size of the board. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty board	Return the null or empty board immediately, as there's nothing to crush.
Board with dimensions 1xN or Nx1	Check for consecutive elements only in the direction that has length greater than or equal to 3.
Board with only one type of candy	Continuously crush until the board stabilizes (no more crushes).
Large board dimensions (performance)	Optimize crushing logic to avoid redundant checks and consider iterative solutions for better performance than recursive ones.
No crushes possible (stable board)	The algorithm should terminate gracefully, returning the original board or indicating stability.
Integer overflow during crush calculation (if using counts)	Use appropriate data types (e.g., long) or avoid direct multiplication of large numbers representing count.
Multiple crushes possible simultaneously (overlapping)	Mark all candies to be crushed in a single pass before actually crushing them, to avoid side effects.
Board filled with zeros	The crushing algorithm should treat zeros as normal candy and check for consecutive occurrences.