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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Zuma Game

Number: 488

Difficulty: Hard

Paid? No

Companies: Zoho, Baidu

Problem Description

Given a row of colored balls on a board (represented as a string) and a set of balls in your hand (also a string), determine the minimum number of balls you need to insert such that, by repeatedly removing any consecutive group of three or more balls of the same color (including cascaded removals), the board becomes empty. Return -1 if it is not possible to clear the board.

Key Insights

  • Use DFS or BFS combined with memoization to explore possible insertion sequences.
  • Represent the hand as a count (frequency) of balls since order does not matter.
  • After each insertion, simulate the cascade removal process by repeatedly eliminating any group of three or more consecutive balls.
  • With board length up to 16 and hand length up to 5, exhaustive search with proper pruning is manageable.

Space and Time Complexity

Time Complexity: In the worst-case scenario, the time complexity is exponential relative to the combined state space of the board and hand; however, given the small input limits, the DFS/BFS with memoization efficiently prunes repeated states. Space Complexity: O(States) where each state is characterized by the current board configuration and hand counts, again practically bounded by the small size of the input.

Solution

We use a DFS (depth-first search) approach combined with memoization to avoid recalculations. The main idea is to try every possible insertion (choosing a ball from the hand and a position on the board), update the board by removing all removable segments via cascading eliminations, and then recursively solve the smaller subproblem. The helper function to remove consecutive balls is critical: it scans the board and repeatedly eliminates any group of three or more consecutive balls of the same color until no more such groups exist.

Data structures:

  • A dictionary (or map) is used for memoization.
  • A frequency dictionary (or array) represents the count of balls in hand.

Algorithmic approach:

  1. Define a helper function to simulate board reduction (cascade removal).
  2. Use DFS to try all possible insertions. For each valid insertion (i.e. when the ball from hand can contribute to an elimination), update the board and hand count.
  3. Return the minimum number of insertions required to eliminate all balls, or -1 if impossible.

This systematic exploration, aided by memoization, efficiently handles the state space by pruning out already computed subproblems.

Code Solutions

# Python solution for Zuma Game

def findMinStep(board: str, hand: str) -> int:
    # Count the balls available in hand for each color
    from collections import Counter
    hand_count = Counter(hand)
    
    # Helper function: recursively remove consecutive balls if they form a group >= 3
    def remove_consecutive(s: str) -> str:
        i = 0
        while i < len(s):
            j = i
            # Move j to the end of the sequence of the same color
            while j < len(s) and s[j] == s[i]:
                j += 1
            # If at least three consecutive same colored balls exist, remove them and restart
            if j - i >= 3:
                s = s[:i] + s[j:]
                i = 0  # restart scanning from beginning
            else:
                i += 1
        return s

    memo = {}
    
    # DFS function returns minimum steps required to clear the board, or a large number if not possible.
    def dfs(s: str, hand_count: dict) -> int:
        if s == "":
            return 0
        # Build a key for memoization using the board string and sorted hand counts
        key = s + ''.join(sorted(color + str(hand_count[color]) for color in hand_count))
        if key in memo:
            return memo[key]
        
        min_steps = float('inf')
        i = 0
        # Try inserting a ball at every possible position in the board
        while i < len(s):
            j = i
            # Skip same color group to avoid repetitive work for same segment start position
            while j < len(s) and s[j] == s[i]:
                j += 1
            need = 3 - (j - i)  # balls needed to remove the current group
            if hand_count[s[i]] >= need:
                # Only consider if we have enough balls. Temporarily reduce the count.
                used = need if need > 0 else 0
                hand_count[s[i]] -= used
                new_board = remove_consecutive(s[:i] + s[i] * need + s[i:j] + s[j:])
                steps = dfs(new_board, hand_count)
                if steps != -1:
                    min_steps = min(min_steps, steps + used)
                hand_count[s[i]] += used  # backtrack the count
            i = j
        
        # If no solution was found, record -1, else record min_steps found.
        memo[key] = -1 if min_steps == float('inf') else min_steps
        return memo[key]
    
    return dfs(board, hand_count)

# Example usage:
if __name__ == '__main__':
    board = "WWRRBBWW"
    hand = "WRBRW"
    print(findMinStep(board, hand))  # Expected output: 2
← Back to All Questions