Skip to main content

488. Zuma Game

hard

Find the minimum balls to insert into a string so all balls are removed, where 3-or-more consecutive same-color balls disappear. The recursion is straightforward; the painful part is the cascade-removal step that must run inside every state.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 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.

Constraints

  • 1 <= board.length <= 16
  • 1 <= 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.

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse on (board state, hand counts).

Hint 2

For every insertion position in the board (0..board.length) and every color in hand: insert the ball, run the chain-removal helper, recurse, take the minimum.

Hint 3

Chain removal: scan for runs of 3+ same color, remove them, repeat until stable.

Hint 4

Memoize on the serialized state. Heuristic: only insert next to a matching ball to prune obvious-dead branches.

Solution approach

Reveal approach

Recursive findMin(board, handCounts) returns the minimum inserts needed. Base case: board is empty -> 0. For each insertion position i in [0, board.length] and each color c with handCounts[c] > 0: form newBoard = board[..i] + c + board[i..], decrement handCounts[c], compute cleaned = collapse(newBoard) (scan for and remove runs of >= 3 same-color repeatedly until stable), recurse on (cleaned, handCounts), increment by 1 if not -1. Track minimum. Restore handCounts[c] after the recursive call. If no insertion clears the board, return -1. Pruning heuristic: skip insert positions where the inserted color doesn't match either neighbor in board — these can never trigger a chain removal in this position. Memoize on (board, sorted hand) to avoid recomputing identical states.

Complexity

Time
O((B + H)! / cache hits)
Space
O(state space)

Related patterns

  • recursion
  • memoization
  • state-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Microsoft
  • Baidu

Practice these live with InterviewChamp.AI

Drill Zuma Game and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →