Zuma Game - Practice Coding Problems

Zuma Game - Problem

You are playing a variation of the game Zuma. In this variation of Zuma, there is a single row of colored balls on a board, where each ball can be colored red 'R', yellow 'Y', blue 'B', green 'G', or white 'W'. You also have several colored balls in your hand.

Your goal is to clear all of the balls from the board. On each turn:

Pick any ball from your hand and insert it in between two balls in the row or on either end of the row.

If there is a group of three or more consecutive balls of the same color, remove the group of balls from the board.

If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.

If there are no more balls on the board, then you win the game.

Repeat this process until you either win or do not have any more balls in your hand.

Given a string board, representing the row of balls on the board, and a string hand, representing the balls in your hand, return the minimum number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return -1.

Input & Output

Example 1 — Basic Clear

$ Input: board = "RWWWRR", hand = "RB"

› Output: 2

💡 Note: Insert B at position 1: RBWWWRR → RBWWWRR (no removal). Insert B at position 2: RBBWWWRR → R___WWWRR (BBB removed) → RWWWRR. Insert R at position 3: RWWRRRR → RWW___ (RRR removed) → RWW. Continue to clear remaining.

Example 2 — Impossible Case

$ Input: board = "RWWWRR", hand = "WWBBRR"

› Output: -1

💡 Note: No matter how we insert the balls, we cannot clear all balls from the board with the given hand.

Example 3 — Already Clear

$ Input: board = "", hand = "RWB"

› Output: 0

💡 Note: Board is already empty, so no moves needed.

Constraints

1 ≤ board.length ≤ 16
0 ≤ hand.length ≤ 5
board and hand consist of characters 'R', 'Y', 'B', 'G', and 'W'
The initial row of balls on the board will not have any groups of three or more consecutive balls of the same color

Visualization

Tap to expand

Understanding the Visualization

Input

Board: RWWWRR, Hand: RB

Strategic Insertions

Insert balls to create groups of 3+ for removal

Chain Reactions

Removals can trigger cascading eliminations

Output

Minimum moves needed: 2

Key Takeaway

🎯 Key Insight: Use BFS with memoization to find the minimum sequence of insertions that creates chain reactions to clear the entire board

Asked in

G Google 12 M Microsoft 8 A Apple 6

The key insight is to use BFS with memoization to systematically explore all possible game states level by level, ensuring we find the minimum number of moves. The algorithm tries inserting each ball at each position, removes consecutive groups, and continues until the board is cleared. Best approach is BFS with memoization. Time: O(2^(n+m) × n²), Space: O(2^(n+m))

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(n! × m^n)	O(n)	Try every possible insertion at every position recursively
BFS with Memoization	O(2^(n+m) × n²)	O(2^(n+m))	Use BFS to find minimum moves with memoization to avoid recomputing states

Brute Force Recursion — Algorithm Steps

Try inserting each ball from hand at each position
Remove groups of 3+ consecutive same colored balls
Recursively solve for the new board state
Return minimum moves across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Each Ball

Pick each ball from hand

Try Each Position

Insert at every possible position

Remove Groups

Remove consecutive groups of 3+

Recurse

Recursively solve remaining state

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

char* removeConsecutive(char* s) {
    int len = strlen(s);
    if (len == 0) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    char* stack = malloc(len + 1);
    int* counts = malloc(len * sizeof(int));
    int stackSize = 0;
    
    for (int i = 0; i < len; i++) {
        if (stackSize > 0 && stack[stackSize - 1] == s[i]) {
            counts[stackSize - 1]++;
        } else {
            stack[stackSize] = s[i];
            counts[stackSize] = 1;
            stackSize++;
        }
    }
    
    char* result = malloc(len + 1);
    int pos = 0;
    for (int i = 0; i < stackSize; i++) {
        if (counts[i] < 3) {
            for (int j = 0; j < counts[i]; j++) {
                result[pos++] = stack[i];
            }
        }
    }
    result[pos] = '\0';
    
    free(stack);
    free(counts);
    
    if (strcmp(result, s) == 0) {
        return result;
    } else {
        char* next = removeConsecutive(result);
        free(result);
        return next;
    }
}

int backtrack(char* board, char* hand) {
    if (strlen(board) == 0) return 0;
    if (strlen(hand) == 0) return INT_MAX;
    
    int minMoves = INT_MAX;
    int handLen = strlen(hand);
    int boardLen = strlen(board);
    
    for (int h = 0; h < handLen; h++) {
        char ball = hand[h];
        
        // Create new hand without this ball
        char* newHand = malloc(handLen);
        int pos = 0;
        for (int i = 0; i < handLen; i++) {
            if (i != h) {
                newHand[pos++] = hand[i];
            }
        }
        newHand[pos] = '\0';
        
        // Try inserting at each position
        for (int i = 0; i <= boardLen; i++) {
            char* newBoard = malloc(boardLen + 2);
            strncpy(newBoard, board, i);
            newBoard[i] = ball;
            strcpy(newBoard + i + 1, board + i);
            
            char* cleanedBoard = removeConsecutive(newBoard);
            int moves = backtrack(cleanedBoard, newHand);
            if (moves != INT_MAX) {
                if (1 + moves < minMoves) {
                    minMoves = 1 + moves;
                }
            }
            
            free(newBoard);
            free(cleanedBoard);
        }
        
        free(newHand);
    }
    
    return minMoves;
}

int solution(char* board, char* hand) {
    int result = backtrack(board, hand);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char board[100], hand[100];
    fgets(board, sizeof(board), stdin);
    fgets(hand, sizeof(hand), stdin);
    board[strcspn(board, "\n")] = 0;
    hand[strcspn(hand, "\n")] = 0;
    
    printf("%d\n", solution(board, hand));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × m^n)

For each of n positions, try m balls, with factorial branching factor

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler