Zuma Game
Zuma Game is a hard graphs problem solved with the bfs for shortest path pattern.
The best approach, optimal (bfs over states with pruned insertions), runs in O(S · m · n²) time and O(S · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dfs over every insertion with memo) up.
Problem
You are playing a ball-shooting game. A row of coloured balls lies on the table, given as the string board, and you hold some balls given as the string hand. Colours are written as the letters R, Y, B, G and W.
In one move you take any ball from your hand and insert it anywhere in the row: at either end or between two balls. Whenever three or more balls of the same colour end up next to each other, that group disappears, and the balls on both sides close the gap; if that creates another group of three or more equal balls, it disappears too, and so on until no such group remains.
Return the minimum number of balls you must insert to clear the whole board, or -1 if it cannot be cleared with the balls in your hand.
Examples
Example 1
- Input
board = "GGBRRBG", hand = "RB"- Output
2- Why
- Put R next to RR: GGB[RRR]BG vanishes, leaving GGBBG. Put B next to BB: GG[BBB]G vanishes, leaving GGG, which vanishes too.
Example 2
- Input
board = "RYRY", hand = "RY"- Output
-1- Why
- The colours alternate, so any insertion only turns a single ball into a pair. With one R and one Y in hand you can never bring three equal balls together.
Example 3
- Input
board = "BBRRBB", hand = "WR"- Output
1- Why
- Insert R into the RR pair: BB[RRR]BB vanishes and the two BB pairs meet as BBBB, which vanishes as well.
Constraints
1 <= board.length <= 161 <= hand.length <= 5boardandhanduse only the lettersR,Y,B,GandW.- The initial board never contains three or more equal balls in a row.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (DFS over every insertion with memo) | O(S · m · n²) | O(S · n) |
| Optimal (BFS over states with pruned insertions) | O(S · m · n²) | O(S · n) |
1Brute force (DFS over every insertion with memo)
O(S · m · n²)S is the number of distinct (board, hand) states reached; each tries up to m colours at n + 1 positions and collapses the board in O(n²) time in the worst case.O(S · n)The memo stores each state's board and hand.Try every distinct colour from the hand at every position of the board, let the board collapse, and recurse with that ball removed from the hand. Memoize on (board, sorted hand) so each state is solved once. A cleared board costs 0; an empty hand with balls still on the board is impossible.
- solve(board, hand): if board is empty return 0; if hand is empty return infinity.
- For each distinct colour c in hand and each position i from 0 to board.length: insert c at i and collapse runs of 3 or more until none remain.
- Candidate = 1 + solve(new board, hand without one c).
- Memoize the minimum; the answer is that value, or -1 if it is infinity.
class Solution {
private final Map<String, Integer> memo = new HashMap<>();
private static final int INF = 1000;
public int findMinStep(String board, String hand) {
char[] h = hand.toCharArray();
Arrays.sort(h);
int r = solve(board, new String(h));
return r >= INF ? -1 : r;
}
private int solve(String board, String hand) {
if (board.isEmpty()) return 0;
if (hand.isEmpty()) return INF;
String key = board + "#" + hand;
Integer cached = memo.get(key);
if (cached != null) return cached;
int best = INF;
for (int j = 0; j < hand.length(); j++) {
if (j > 0 && hand.charAt(j) == hand.charAt(j - 1)) continue;
char c = hand.charAt(j);
String rest = hand.substring(0, j) + hand.substring(j + 1);
for (int i = 0; i <= board.length(); i++) {
String next = collapse(board.substring(0, i) + c + board.substring(i));
best = Math.min(best, 1 + solve(next, rest));
}
}
memo.put(key, best);
return best;
}
private String collapse(String b) {
boolean found = true;
while (found) {
found = false;
int i = 0;
while (i < b.length()) {
int j = i;
while (j < b.length() && b.charAt(j) == b.charAt(i)) j++;
if (j - i >= 3) {
b = b.substring(0, i) + b.substring(j);
found = true;
break;
}
i = j;
}
}
return b;
}
}class Solution:
def findMinStep(self, board: str, hand: str) -> int:
INF = 1000
memo = {}
def collapse(b: str) -> str:
found = True
while found:
found = False
i = 0
while i < len(b):
j = i
while j < len(b) and b[j] == b[i]:
j += 1
if j - i >= 3:
b = b[:i] + b[j:]
found = True
break
i = j
return b
def solve(b: str, h: str) -> int:
if not b:
return 0
if not h:
return INF
key = (b, h)
if key in memo:
return memo[key]
best = INF
for j in range(len(h)):
if j > 0 and h[j] == h[j - 1]:
continue
c = h[j]
rest = h[:j] + h[j + 1:]
for i in range(len(b) + 1):
best = min(best, 1 + solve(collapse(b[:i] + c + b[i:]), rest))
memo[key] = best
return best
r = solve(board, ''.join(sorted(hand)))
return -1 if r >= INF else rclass Solution {
public:
int findMinStep(string board, string hand) {
sort(hand.begin(), hand.end());
int r = solve(board, hand);
return r >= INF ? -1 : r;
}
private:
static const int INF = 1000;
unordered_map<string, int> memo;
int solve(const string& board, const string& hand) {
if (board.empty()) return 0;
if (hand.empty()) return INF;
string key = board + "#" + hand;
auto it = memo.find(key);
if (it != memo.end()) return it->second;
int best = INF;
for (int j = 0; j < (int)hand.size(); j++) {
if (j > 0 && hand[j] == hand[j - 1]) continue;
char c = hand[j];
string rest = hand.substr(0, j) + hand.substr(j + 1);
for (int i = 0; i <= (int)board.size(); i++) {
string next = collapse(board.substr(0, i) + c + board.substr(i));
best = min(best, 1 + solve(next, rest));
}
}
memo[key] = best;
return best;
}
string collapse(string b) {
bool found = true;
while (found) {
found = false;
int i = 0;
while (i < (int)b.size()) {
int j = i;
while (j < (int)b.size() && b[j] == b[i]) j++;
if (j - i >= 3) {
b = b.substr(0, i) + b.substr(j);
found = true;
break;
}
i = j;
}
}
return b;
}
};function findMinStep(board, hand) {
const INF = 1000;
const memo = new Map();
const collapse = (b) => {
let found = true;
while (found) {
found = false;
let i = 0;
while (i < b.length) {
let j = i;
while (j < b.length && b[j] === b[i]) j++;
if (j - i >= 3) {
b = b.slice(0, i) + b.slice(j);
found = true;
break;
}
i = j;
}
}
return b;
};
const solve = (b, h) => {
if (b.length === 0) return 0;
if (h.length === 0) return INF;
const key = b + '#' + h;
if (memo.has(key)) return memo.get(key);
let best = INF;
for (let j = 0; j < h.length; j++) {
if (j > 0 && h[j] === h[j - 1]) continue;
const c = h[j];
const rest = h.slice(0, j) + h.slice(j + 1);
for (let i = 0; i <= b.length; i++)
best = Math.min(best, 1 + solve(collapse(b.slice(0, i) + c + b.slice(i)), rest));
}
memo.set(key, best);
return best;
};
const r = solve(board, hand.split('').sort().join(''));
return r >= INF ? -1 : r;
}2Optimal (BFS over states with pruned insertions)
O(S · m · n²)Same state bound as before, but the pruning cuts the positions per colour to the few useful ones, so far fewer states are generated, and BFS stops at the first solution.O(S · n)The visited set and the queue.Breadth-first search over (board, sorted hand) states finds the fewest balls, and stops at the first cleared board. Most insertions are pointless, so only two kinds are tried: placing a ball directly before an equal ball (it grows that group), or placing it between two equal balls of another colour (it splits them so a later collapse can reconnect them in a chain reaction). Inserting right after an equal ball is skipped because it gives the same board as inserting before that ball. Equal colours in the sorted hand are tried once.
- Queue the start state (board, sorted hand) with 0 moves and mark it visited.
- Pop a state. For each distinct colour c in the hand and each position i: skip if board[i-1] == c.
- Keep only i with board[i] == c, or with board[i-1] == board[i] != c.
- Insert, collapse runs of 3 or more; if the board is empty return moves + 1.
- Otherwise enqueue the new state if it was not visited. If the queue empties, return -1.
class Solution {
public int findMinStep(String board, String hand) {
char[] h = hand.toCharArray();
Arrays.sort(h);
String start = new String(h);
Deque<String[]> queue = new ArrayDeque<>();
Set<String> seen = new HashSet<>();
queue.offer(new String[] { board, start });
seen.add(board + "#" + start);
int steps = 0;
while (!queue.isEmpty()) {
steps++;
for (int size = queue.size(); size > 0; size--) {
String[] cur = queue.poll();
String b = cur[0], hd = cur[1];
for (int j = 0; j < hd.length(); j++) {
char c = hd.charAt(j);
if (j > 0 && hd.charAt(j - 1) == c) continue;
String rest = hd.substring(0, j) + hd.substring(j + 1);
for (int i = 0; i <= b.length(); i++) {
if (i > 0 && b.charAt(i - 1) == c) continue;
boolean grow = i < b.length() && b.charAt(i) == c;
boolean split = i > 0 && i < b.length() && b.charAt(i - 1) == b.charAt(i) && b.charAt(i) != c;
if (!grow && !split) continue;
String nb = collapse(b.substring(0, i) + c + b.substring(i));
if (nb.isEmpty()) return steps;
if (seen.add(nb + "#" + rest)) queue.offer(new String[] { nb, rest });
}
}
}
}
return -1;
}
private String collapse(String b) {
boolean found = true;
while (found) {
found = false;
int i = 0;
while (i < b.length()) {
int j = i;
while (j < b.length() && b.charAt(j) == b.charAt(i)) j++;
if (j - i >= 3) {
b = b.substring(0, i) + b.substring(j);
found = true;
break;
}
i = j;
}
}
return b;
}
}class Solution:
def findMinStep(self, board: str, hand: str) -> int:
def collapse(b: str) -> str:
found = True
while found:
found = False
i = 0
while i < len(b):
j = i
while j < len(b) and b[j] == b[i]:
j += 1
if j - i >= 3:
b = b[:i] + b[j:]
found = True
break
i = j
return b
start = ''.join(sorted(hand))
queue = deque([(board, start)])
seen = {(board, start)}
steps = 0
while queue:
steps += 1
for _ in range(len(queue)):
b, h = queue.popleft()
for j in range(len(h)):
c = h[j]
if j > 0 and h[j - 1] == c:
continue
rest = h[:j] + h[j + 1:]
for i in range(len(b) + 1):
if i > 0 and b[i - 1] == c:
continue
grow = i < len(b) and b[i] == c
split = 0 < i < len(b) and b[i - 1] == b[i] and b[i] != c
if not grow and not split:
continue
nb = collapse(b[:i] + c + b[i:])
if not nb:
return steps
if (nb, rest) not in seen:
seen.add((nb, rest))
queue.append((nb, rest))
return -1class Solution {
public:
int findMinStep(string board, string hand) {
sort(hand.begin(), hand.end());
queue<pair<string, string>> q;
unordered_set<string> seen;
q.push({board, hand});
seen.insert(board + "#" + hand);
int steps = 0;
while (!q.empty()) {
steps++;
for (int size = q.size(); size > 0; size--) {
auto [b, hd] = q.front();
q.pop();
for (int j = 0; j < (int)hd.size(); j++) {
char c = hd[j];
if (j > 0 && hd[j - 1] == c) continue;
string rest = hd.substr(0, j) + hd.substr(j + 1);
for (int i = 0; i <= (int)b.size(); i++) {
if (i > 0 && b[i - 1] == c) continue;
bool grow = i < (int)b.size() && b[i] == c;
bool split = i > 0 && i < (int)b.size() && b[i - 1] == b[i] && b[i] != c;
if (!grow && !split) continue;
string nb = collapse(b.substr(0, i) + c + b.substr(i));
if (nb.empty()) return steps;
if (seen.insert(nb + "#" + rest).second) q.push({nb, rest});
}
}
}
}
return -1;
}
private:
string collapse(string b) {
bool found = true;
while (found) {
found = false;
int i = 0;
while (i < (int)b.size()) {
int j = i;
while (j < (int)b.size() && b[j] == b[i]) j++;
if (j - i >= 3) {
b = b.substr(0, i) + b.substr(j);
found = true;
break;
}
i = j;
}
}
return b;
}
};function findMinStep(board, hand) {
const collapse = (b) => {
let found = true;
while (found) {
found = false;
let i = 0;
while (i < b.length) {
let j = i;
while (j < b.length && b[j] === b[i]) j++;
if (j - i >= 3) {
b = b.slice(0, i) + b.slice(j);
found = true;
break;
}
i = j;
}
}
return b;
};
const start = hand.split('').sort().join('');
let queue = [[board, start]];
const seen = new Set([board + '#' + start]);
let steps = 0;
while (queue.length > 0) {
steps++;
const next = [];
for (const [b, h] of queue) {
for (let j = 0; j < h.length; j++) {
const c = h[j];
if (j > 0 && h[j - 1] === c) continue;
const rest = h.slice(0, j) + h.slice(j + 1);
for (let i = 0; i <= b.length; i++) {
if (i > 0 && b[i - 1] === c) continue;
const grow = i < b.length && b[i] === c;
const split = i > 0 && i < b.length && b[i - 1] === b[i] && b[i] !== c;
if (!grow && !split) continue;
const nb = collapse(b.slice(0, i) + c + b.slice(i));
if (nb.length === 0) return steps;
const key = nb + '#' + rest;
if (!seen.has(key)) {
seen.add(key);
next.push([nb, rest]);
}
}
}
}
queue = next;
}
return -1;
}Edge cases to test
- A ball that is not needed at all: the answer can use fewer balls than the hand holds
- Chain reactions, where one removal makes two neighbouring groups meet
- Boards that only clear if a ball is inserted between two equal balls to split them, like RRWWRRBBRR with hand WB
- A colour on the board that never appears in the hand
- Impossible boards, where the answer is -1
Hints
Hint 1
The sizes are tiny (at most 16 balls on the board and 5 in hand), so exploring every sequence of moves is realistic if you avoid repeated work.
Hint 2
A state is the current board plus the multiset of balls left in hand. Breadth-first search over states finds the fewest moves; sort the hand so equal multisets compare equal.
Hint 3
Most insertions are useless. It is enough to insert a ball right before an equal ball, or between two equal balls of a different colour (to split them so a later chain reaction can happen).
FAQ
What is the best time complexity for Zuma Game?
Optimal (BFS over states with pruned insertions) runs in O(S · m · n²) time and O(S · n) extra space. Same state bound as before, but the pruning cuts the positions per colour to the few useful ones, so far fewer states are generated, and BFS stops at the first solution.
Which pattern does Zuma Game use?
It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.
Is there a brute force solution for Zuma Game?
Yes. Brute force (DFS over every insertion with memo) takes O(S · m · n²) time and O(S · n) space. Try every distinct colour from the hand at every position of the board, let the board collapse, and recurse with that ball removed from the hand.
Which edge cases should I test for Zuma Game?
A ball that is not needed at all: the answer can use fewer balls than the hand holds; Chain reactions, where one removal makes two neighbouring groups meet; Boards that only clear if a ball is inserted between two equal balls to split them, like RRWWRRBBRR with hand WB; A colour on the board that never appears in the hand; Impossible boards, where the answer is -1.