Zuma Game

Hard Graphs BFS for shortest path Original on LeetCode

Reported atPhonePeInMobi

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 <= 16
  • 1 <= hand.length <= 5
  • board and hand use only the letters R, Y, B, G and W.
  • 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(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.
SpaceO(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.

  1. solve(board, hand): if board is empty return 0; if hand is empty return infinity.
  2. 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.
  3. Candidate = 1 + solve(new board, hand without one c).
  4. 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;
    }
}

2Optimal (BFS over states with pruned insertions)

TimeO(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.
SpaceO(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.

  1. Queue the start state (board, sorted hand) with 0 moves and mark it visited.
  2. Pop a state. For each distinct colour c in the hand and each position i: skip if board[i-1] == c.
  3. Keep only i with board[i] == c, or with board[i-1] == board[i] != c.
  4. Insert, collapse runs of 3 or more; if the board is empty return moves + 1.
  5. 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;
    }
}

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.