Zuma Game - Solution & Explanation

Q: Is Zuma Game easy or hard?

Zuma Game is classified as a Hard problem on LeetCode. The challenge comes from modeling the board state, handling chain reactions after removals, and pruning the exponential search space using memoization.

Q: Zuma Game Python/Java solution

Python and C++ solutions often implement DFS backtracking with memoization using dictionaries or unordered maps. Java and JavaScript implementations sometimes demonstrate greedy insertion simulations, though DFS with caching is still the optimal strategy.

Q: How to solve Zuma Game in O(n)?

An O(n) solution does not exist for the full problem because you must explore many insertion sequences to guarantee the minimum moves. The closest practical method is DFS with memoization, which prunes repeated states but still has exponential worst‑case behavior.

Q: What is the best approach for Zuma Game?

The most reliable approach uses DFS backtracking with memoization. Each recursion tries inserting balls at different positions, then collapses groups of three or more. Memoization caches previously seen board and hand states to avoid recomputation, reducing the exponential search significantly.

Q: Is Zuma Game asked at Google/Amazon/Meta?

Zuma Game represents the type of hard backtracking and state search problem occasionally asked in top tech interviews. Variants involving board reduction, recursive search, and memoization have appeared in interviews at companies like Google and Meta.

Q: What data structure is used in Zuma Game?

The solution typically uses strings to represent the board, hash maps for memoization, and sometimes stack-style scans to remove consecutive groups. DFS recursion manages the state exploration while memo tables cache previously computed results.

Q: What is the time complexity of Zuma Game?

The DFS search explores many insertion combinations, leading to exponential complexity in the worst case, often approximated as O(b^h * n) where b is branching factor and h is hand size. Memoization and pruning reduce repeated states, making it feasible for the constraints used in the problem.

HardString Dynamic Programming Stack Breadth-First Search13 min readAsked at: Amazon, Baidu, Google +4

Practice this problem

Problem Statement

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.

Example 1:

Input: board = "WRRBBW", hand = "RB"
Output: -1
Explanation: It is impossible to clear all the balls. The best you can do is:
- Insert 'R' so the board becomes WRRRBBW. WRRRBBW -> WBBW.
- Insert 'B' so the board becomes WBBBW. WBBBW -> WW.
There are still balls remaining on the board, and you are out of balls to insert.

Example 2:

Input: board = "WWRRBBWW", hand = "WRBRW"
Output: 2
Explanation: To make the board empty:
- Insert 'R' so the board becomes WWRRRBBWW. WWRRRBBWW -> WWBBWW.
- Insert 'B' so the board becomes WWBBBWW. WWBBBWW -> WWWW -> empty.
2 balls from your hand were needed to clear the board.

Example 3:

Input: board = "G", hand = "GGGGG"
Output: 2
Explanation: To make the board empty:
- Insert 'G' so the board becomes GG.
- Insert 'G' so the board becomes GGG. GGG -> empty.
2 balls from your hand were needed to clear the board.

Constraints:

1 <= board.length <= 16
1 <= hand.length <= 5
board and hand consist of the 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.

Approach Overview

Problem Overview: You are given a board string representing colored balls and a hand containing extra balls. Insert balls anywhere on the board so that whenever three or more consecutive balls of the same color appear, they disappear and may trigger chain reactions. The goal is to clear the entire board using the minimum number of insertions.

Approach 1: Backtracking with DFS + Memoization (Time: O(b^h * n), Space: O(b^h))

This problem is naturally modeled as a recursive search. At every step, try inserting a ball from the hand into every possible position on the board. After each insertion, simulate removals by repeatedly collapsing sequences of length ≥3 using a stack-like elimination pass. The recursion continues with the updated board and remaining hand until the board becomes empty. Because many board-hand combinations repeat, memoization caches states like (board, handCount) to avoid recomputation. This drastically prunes the search space and makes the solution practical even though the theoretical complexity is exponential.

The key insight is that only insertions that can help form or extend groups are useful. Pruning invalid placements and normalizing the board after every insertion keeps the state small. This approach heavily relies on string manipulation and memoization to explore the state space efficiently.

Approach 2: Greedy Iteration for Partial Progress (Time: O(n^2 * k), Space: O(n))

A simpler heuristic approach repeatedly scans the board looking for places where inserting a ball can immediately create or extend a group of three. For example, if the board has RR and the hand contains R, inserting it removes the group instantly. After each insertion, perform a collapse pass that removes any chain reactions. This strategy iterates until no more progress is possible or the board clears.

This method is easier to implement but does not explore all states, so it may miss the optimal sequence in tricky cases. It still works reasonably well when the board contains many near-complete groups. The elimination step often uses a stack-like scan similar to solutions for parentheses reduction or candy crush style problems, connecting it conceptually to stack based reductions.

Recommended for interviews: Backtracking with DFS and memoization is the expected solution. Interviewers want to see how you model the game state, prune invalid insertions, and cache repeated states. The greedy approach shows intuition but does not guarantee optimal results. Demonstrating the recursive search combined with memoization signals strong understanding of state-space exploration and optimization techniques.

Approach 1: Backtracking with DFS

This approach utilizes a Depth First Search (DFS) with backtracking strategy. The idea is to try inserting each ball in the hand between each position of the board recursively and track the number of moves to clear the board. Whenever a group of 3 or more balls is formed, it's immediately removed.

Steps:

Define a recursive DFS function that tries every possible insertion for each ball in the hand.
At each insertion attempt, check if a consecutive group of 3 or more balls is formed and remove them.
Keep track of the minimum number of insertions needed to remove all balls. If a position has been visited with fewer balls in hand, do not proceed with that path.
If the board is empty, record the minimum steps and backtrack.
If it becomes impossible to clear the board, return -1.

The given Python solution employs DFS with backtracking to explore each possible move by inserting balls into the board. A helper function, remove_consecutives, removes any three or more consecutive balls. In each DFS recursion, it checks for all possible places to insert a ball from the hand. If a group of three or more is formed, it recursively checks the reduced board state.

Code

Python C++

Python

C++

Complexity

Time Complexity: Between O(3⁷) and O(5¹⁶), worst case depending on hand and board length.

Space Complexity: O(n + h), where n is the board length and h is the hand length for recursion depth.

Try this approach in the editor →

Approach 2: Greedy with Iteration for Partial Progress

Though the problem typically requires a full DFS due to its complexity, a greedy solution can sometimes deliver partial solutions or be used to generate helpful heuristics. This method focuses on making moves that immediately reduce the current board length or solve the most straightforward remaining groups. While not fully solving the problem, this can reduce the state space for a subsequent DFS.

The JavaScript solution aims to apply a memory-optimized DFS approach. Memoization avoids recalculating similar states. The shrink function is responsible for handling chains of ball collapses that naturally emerge due to insertions, ensuring full collapses are efficiently processed.

Code

JavaScript Java

JavaScript

Java

Complexity

Time Complexity: Depends on number of valid permutations of board and hand, typically between O(3⁷) to O(5¹⁶).

Space Complexity: O(n + h) for depth state in dfs and memoization overhead.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java

Python

Java

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Backtracking with DFS	Time Complexity: Between O(3⁷) and O(5¹⁶), worst case depending on hand and board length. Space Complexity: O(n + h), where n is the board length and h is the hand length for recursion depth.
Greedy with Iteration for Partial Progress	Time Complexity: Depends on number of valid permutations of board and hand, typically between O(3⁷) to O(5¹⁶). Space Complexity: O(n + h) for depth state in dfs and memoization overhead.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Backtracking DFS with Memoization	O(b^h * n)	O(b^h)	General case when you must guarantee the minimum number of insertions
Greedy Iteration with Collapse Simulation	O(n^2 * k)	O(n)	Useful for quick partial solutions or when the board has many near-complete groups

Video Solution

花花酱 LeetCode 488. Zuma Game - 刷题找工作 EP84 • Hua Hua • 4,936 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Zuma Game easy or hard?

Zuma Game is classified as a Hard problem on LeetCode. The challenge comes from modeling the board state, handling chain reactions after removals, and pruning the exponential search space using memoization.

Zuma Game Python/Java solution

Python and C++ solutions often implement DFS backtracking with memoization using dictionaries or unordered maps. Java and JavaScript implementations sometimes demonstrate greedy insertion simulations, though DFS with caching is still the optimal strategy.

How to solve Zuma Game in O(n)?

An O(n) solution does not exist for the full problem because you must explore many insertion sequences to guarantee the minimum moves. The closest practical method is DFS with memoization, which prunes repeated states but still has exponential worst‑case behavior.

What is the best approach for Zuma Game?

The most reliable approach uses DFS backtracking with memoization. Each recursion tries inserting balls at different positions, then collapses groups of three or more. Memoization caches previously seen board and hand states to avoid recomputation, reducing the exponential search significantly.

Is Zuma Game asked at Google/Amazon/Meta?

Zuma Game represents the type of hard backtracking and state search problem occasionally asked in top tech interviews. Variants involving board reduction, recursive search, and memoization have appeared in interviews at companies like Google and Meta.

What data structure is used in Zuma Game?

The solution typically uses strings to represent the board, hash maps for memoization, and sometimes stack-style scans to remove consecutive groups. DFS recursion manages the state exploration while memo tables cache previously computed results.

What is the time complexity of Zuma Game?

The DFS search explores many insertion combinations, leading to exponential complexity in the worst case, often approximated as O(b^h * n) where b is branching factor and h is hand size. Memoization and pruning reduce repeated states, making it feasible for the constraints used in the problem.

Ready to solve this problem?

Practice Zuma Game with our built-in code editor and test cases.

Practice on FleetCode

Longest Substring Without Repeating Characters

Longest Palindromic Substring

Problem Info

DifficultyHard

Acceptance29.4%

Approaches3

Reading time13 min

Asked at

Amazon Baidu Google Zoho PhonePe

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Backtracking with DFS

Code

Complexity

Approach 2: Greedy with Iteration for Partial Progress

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents