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'.Zuma Game is a challenging search problem where the goal is to remove all balls from the board using the minimum number of insertions from your hand. The key difficulty lies in exploring different insertion possibilities while efficiently handling chain reactions that remove groups of three or more balls.
A common strategy is to use Breadth-First Search (BFS) over game states. Each state represents the current board configuration and remaining hand balls. After inserting a ball, a helper routine repeatedly removes consecutive groups of three or more to simulate the board collapse. BFS guarantees the minimum number of steps because it explores states level by level.
Another effective approach combines DFS with memoization or dynamic programming. By caching previously computed board-hand combinations, repeated exploration is avoided. Efficient string reduction and pruning are critical for performance. With careful state management, the algorithm explores only meaningful transitions.
Although the search space can grow quickly, pruning and memoization keep it manageable for interview constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS State Exploration | Exponential in board length due to branching of insertions | O(N * states) for queue and visited states |
| DFS with Memoization | Exponential worst case, reduced by caching repeated states | O(states) for memoization storage |
Amr
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Zuma Game represents the type of complex state-search and backtracking problem sometimes seen in top tech interviews. While the exact question may vary, similar problems involving BFS, memoization, and state compression are common in FAANG-level preparation.
Many board and hand combinations can appear multiple times during the search. Memoization stores previously computed results so the algorithm does not recompute them. This significantly reduces the effective search space.
A common optimal strategy uses BFS to explore all possible board states after inserting balls from the hand. Since BFS processes states level by level, it guarantees the minimum number of moves. Memoization or visited-state tracking helps avoid recomputing identical configurations.
Strings are typically used to represent the board state, while hash maps or sets store visited configurations. Queues support BFS traversal, and memoization maps help cache results in DFS solutions.