We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Candy Crush

Number: 723

Difficulty: Medium

Paid? Yes

Companies: Capital One, Meta, Bloomberg, Uber, Rubrik

Problem Description

We are given an m x n grid representing a Candy Crush board where each cell contains a positive integer for a type of candy, or 0 representing an empty cell. The task is to repeatedly "crush" (set to 0) candies in groups of three or more that are adjacent horizontally or vertically. Once crushed, the candies above drop down into the empty spaces, and this process is repeated until no more candies can be crushed and the board is stable.

Key Insights

  • Use a simulation approach: repeatedly detect crushable candies and simulate their removal.
  • Traverse horizontally and vertically to mark candies that are in groups of three or more.
  • Instead of removing candies immediately, mark them for removal and update the board once for the entire pass.
  • After crushing, simulate gravity by shifting non-zero candies downward in each column.
  • Continue the process until no further candy crushes can be detected.

Space and Time Complexity

Time Complexity: O((mn)^2) in the worst case since each iteration includes scanning the m x n grid and then applying gravity. Space Complexity: O(mn) for maintaining additional markers or flags (or using the board itself with in-place modifications).

Solution

The approach involves iteratively scanning the board to identify candy groups that should be crushed using two passes:

  1. Horizontal Check – For each row, check segments of 3 consecutive candies.
  2. Vertical Check – For each column, check segments of 3 consecutive candies. If any candy qualifies, mark its position for crushing. After marking, update the board by turning all marked positions into 0. Then, for each column, drop down non-zero candies such that all empty cells (zeros) are at the top. Repeat this process until no group of 3 or more adjacent candies is found. Key data structures include the board array and a temporary marker (can be implicit by using signs or a separate boolean matrix) for tracking candies to crush. The algorithm ensures a stable board before returning it.

Code Solutions

def candyCrush(board):
    # Retrieve board dimensions
    m, n = len(board), len(board[0])
    # Loop until no crushable candies remain
    while True:
        # Set to hold all positions that need to be crushed
        crush_set = set()
        
        # Check horizontally for crushable candies
        for i in range(m):
            for j in range(n - 2):
                # Check if candy exists and three consecutive candies are the same
                if board[i][j] != 0 and abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2]):
                    crush_set |= {(i, j), (i, j+1), (i, j+2)}
        
        # Check vertically for crushable candies
        for i in range(m - 2):
            for j in range(n):
                if board[i][j] != 0 and abs(board[i][j]) == abs(board[i+1][j]) == abs(board[i+2][j]):
                    crush_set |= {(i, j), (i+1, j), (i+2, j)}
        
        # If no candies need to be crushed, the board is stable; break out of the loop.
        if not crush_set:
            break
        
        # Set all marked positions to 0 (simulate crushing)
        for i, j in crush_set:
            board[i][j] = 0
        
        # Apply gravity: For each column, move uncrushed candies downwards
        for j in range(n):
            # Pointer for placing the next candy from bottom-up
            write_index = m - 1
            # Traverse each column from bottom to top
            for i in range(m - 1, -1, -1):
                if board[i][j] != 0:
                    board[write_index][j] = board[i][j]
                    write_index -= 1
            # Fill remaining positions with 0
            for i in range(write_index, -1, -1):
                board[i][j] = 0
                
    return board

# Example usage:
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]]
print(candyCrush(board))
← Back to All Questions