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.
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:
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.
Time Complexity: Between O(37) and O(516), 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.
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.
JavaScript
Java
Time Complexity: Depends on number of valid permutations of board and hand, typically between O(37) to O(516).
Space Complexity: O(n + h) for depth state in dfs and memoization overhead.
| Approach | Complexity |
|---|---|
| Backtracking with DFS | Time Complexity: Between O(37) and O(516), 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(37) to O(516). Space Complexity: O(n + h) for depth state in dfs and memoization overhead. |
| Default Approach | — |
| 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 |
花花酱 LeetCode 488. Zuma Game - 刷题找工作 EP84 • Hua Hua • 4,904 views views
Watch 7 more video solutions →Practice Zuma Game with our built-in code editor and test cases.
Practice on FleetCode