Watch 8 video solutions for Zuma Game, a hard level problem involving String, Dynamic Programming, Stack. This walkthrough by Hua Hua has 4,904 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 <= 161 <= hand.length <= 5board and hand consist of the characters 'R', 'Y', 'B', 'G', and 'W'.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 | 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 |