488. Zuma Game

HardStackBreadth-First SearchMemoizationStringDynamic Programming

Problem Description

The problem presents a game which is similar to Zuma where there is a single row of colored balls on a board, and the player has several balls in their hand of potentially different colors. The goal is to clear all of the balls from the board. On each turn, the player can insert a ball from their hand into the row either between two existing balls or at either end. If inserting the ball creates a sequence of three or more consecutive balls of the same color, that group is removed. The removal of balls can cause a chain reaction, leading to the removal of additional groups of balls if new groups of three or more are made. The process continues until all balls are cleared or the player runs out of balls.

A string board represents the row of balls on the board, while another string hand represents the balls in the player's hand. Each ball is represented by a character indicating its color: 'R' for red, 'Y' for yellow, 'B' for blue. 'G' for green, and 'W' for white. The task is to return the minimum number of balls the player has to insert to clear the board. If the player cannot clear the board, the function should return -1.

Flowchart Walkthrough

Let's use the algorithm flowchart to determine the most suitable algorithm for solving Leetcode 488, Zuma Game. Here’s a step-by-step walkthrough using the Flowchart:

Is it a graph?

Yes: Although not in a traditional sense of nodes and edges, the Zuma Game problem involves states and transitions between them, resembling a graph where each state can be considered a node and each possible action (inserting a ball) can be considered an edge creating a new state.

Is it a tree?

No: The problem's state could have multiple ways to reach the same game state due to different sequences of actions, so the states do not form a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: This problem is primarily focused on finding an optimal sequence of actions (minimal ball insertions), which does not involve processing DAG properties like topology.

Is the problem related to shortest paths?

Yes: Fundamentally, the problem looks for the shortest sequence of moves (minimal insertions) that clears the board, akin to finding a shortest transformation path in a graph.

Is the graph weighted?

No: Each move (or transformation from one state to another) typically has an equal cost or weight in the context of this game (each insertion counts uniformly).

Does the problem involve connectivity?

No: Unlike connectivity problems that focus on the relationship between distinct nodes or components, this problem deals with the efficiency of transformations between states.

Does the problem have small constraints?

No: Given the potentially large number of combinations and moves, the constraints can't be considered small, even if optimized approaches are necessary to handle efficiency.

Conclusion: Based on the flowchart, we could use BFS for this problem. While the question doesn't drone on shortest paths in traditional sense (like in a physical or networked environment), it does require exploring levels or layers of game states created by each move, making BFS suitable to ensure all states at a given level of minimal moves are explored before moving on to states requiring more moves. This characteristic aligns with Breadth-First Search's layer-by-layer approach.

Intuition

The solution approach involves processing the game's turns and simulating the changes on the board using recursion or iteration. The intuition is to try all possible moves and apply the move that leads to the best outcome (clearing the board with the fewest moves).

The primary idea behind the recursive solution is to use a breadth-first search (BFS) strategy to explore each possible state of the board. Starting with the initial state of the board, we insert all possible balls from the hand into all possible positions on the board, one by one, in all possible ways. After each insertion, we remove contiguous groups of balls that match the three-or-more condition. We use a queue to keep track of the different game states that result from each move.

A visited set is essential to avoid processing the same state multiple times, thus optimizing the performance by not re-exploring already visited states.

To remove the consecutive balls, we can apply a regex replace operation to find patterns of three or more consecutive balls of the same color and replace them with an empty string, effectively removing them from the board.

BFS ensures that when we clear the board, the solution we have reached is the minimal number of steps needed because BFS explores solutions in increasing order of depth i.e., turns taken. The moment the board is empty, it indicates that the optimal solution is found, hence we stop the search and return the minimum steps taken, which is the initial number of balls in hand minus the number of balls remaining in hand.

If the queue gets exhausted, and we have not cleared the board, we can be sure that no valid moves are left; hence, we return -1.

Learn more about Stack, Breadth-First Search, Memoization and Dynamic Programming patterns.

Solution Approach

The implementation of the solution consists of several key parts that work together to find the minimum number of steps required to clear the board:

Recursive Removal Function: A helper function remove is defined to recursively remove consecutive balls of the same color (three or more) from the board. This function uses the re.sub method from the re module to perform a regular expression substitution. r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}' is the regular expression pattern that matches any sequence of three or more balls of the same color and replaces them with an empty string. The function continues to remove sequences until no more can be removed, then returns the resulting string.
Breadth-first Search (BFS): BFS is initiated using a queue (collections.deque) to keep track of all possible board configurations and the remaining balls in the hand after each turn. The queue is initialized with the starting state of the board and hand.
Visited States: A set named visited tracks the states that have been explored to avoid re-processing them.
Processing Each State: When processing each state from the queue, the algorithm looks for all places the ball from the hand can be inserted (each possible index in the string representing the board). The ball is inserted and the remove function is then called to clear the board of any sequences of three or more identical balls. Each possible new state—after the ball is inserted and sequences are removed—is checked to ensure it has not already been visited. If it hasn't, it is added to the queue to be processed. The balls in hand are decremented by one for the color of the ball used.
Winning Condition: If, after any removal, the board is empty (if not state), then all the balls have been cleared. The algorithm returns the difference between the original number of balls in hand and the current number of balls in hand as the minimum number of steps taken to clear the board.
Loop Continuation & Termination: The loop continues until there are no more states left in the queue to process. If the queue is exhausted before the board is cleared, this means it is impossible to clear the board with the given balls in hand, hence -1 is returned.

By combining these mechanisms, the Solution efficiently explores all possibilities and correctly identifies the minimum number of steps, if any, to solve the given Zuma variation.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Suppose we have the following game state:

Board: WRRBBW
Hand: RB

Following the solution approach:

Recursive Removal Function: This function removes any sequence of three or more balls of the same color on the board. So, if we insert an 'R' between 'RR', we'd have 'RRR' which would be removed by this function.
BFS Initial State: We start with a queue containing a tuple with our current board WRRBBW and the hand RB.
Exploring States: We take the first state from the queue and try all possible moves. Here are a few:
- Insert 'R' between 'W' and 'RR'. New board would be WRRRBBW, which will trigger removal and result in WBBW.
- Insert 'R' at the end. New board WRRBBWR. No removal is triggered since we don't have three 'R's in a row.
Visited States: Let's say we choose to insert 'R' between 'W' and 'RR', so the new non-visited state is WBBW, with a hand of B.
Removals and State Updates: We continue with state WBBW and hand B. We insert 'B' between 'BB', and the new board is WBBBBW. This triggers a removal, clearing all 'B's and resulting in WW.
- After removal, the board is WW, and the hand is empty.
End Condition: The board is not empty yet, but we have no balls left in our hand. Since we reached the end of potential moves without clearing the board, this path did not lead to a solution.
Other Paths: Had there been more balls in the hand, we would continue exploring by inserting them into the board and following the same process.
Completion or Failure: Continuing this way, we explore all possible insertion positions for each ball in hand. If at any point the board becomes empty, we have found a successful sequence of moves, and we return the number of moves made. If we exhaust all options without clearing the board, we return -1, indicating failure.

In our example, with only two balls in hand (one 'R' and one 'B'), and the original board configuration of WRRBBW, there is no sequence of moves we could make to clear the board completely, and we would have to return -1.

Solution Implementation

1from collections import deque
2import re
3
4class Solution:
5    def findMinStep(self, board: str, hand: str) -> int:
6        # Helper function to remove sequences of three or more identical balls
7        def remove_consecutive(s: str) -> str:
8            while True:
9                # Replace sequences of the same ball that are 3 or more in length with empty string
10                next_str = re.sub(r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}', '', s)
11                # If no such sequences are found, stop the loop
12                if len(next_str) == len(s):
13                    break
14                s = next_str
15            return s
16
17        visited = set()  # Set to track visited states to avoid duplicates
18        queue = deque([(board, hand)])  # Queue for BFS with initial state
19
20        while queue:
21            current_board, remaining_balls = queue.popleft()
22            # If the board is empty, return the number of balls used
23            if not current_board:
24                return len(hand) - len(remaining_balls)
25            for ball in set(remaining_balls):  # Iterate through unique balls
26                next_balls = remaining_balls.replace(ball, '', 1)  # Remove a ball from the hand
27                for i in range(len(current_board) + 1):
28                    # Insert the ball into every possible position on the board
29                    new_board = current_board[:i] + ball + current_board[i:]
30                    new_board = remove_consecutive(new_board)  # Remove consecutive sequences
31                    if new_board not in visited:
32                        visited.add(new_board)  # Mark the new board as visited
33                        queue.append((new_board, next_balls))  # Queue the new state
34
35        return -1  # Return -1 if no solution is found
36
37# Example usage:
38# sol = Solution()
39# print(sol.findMinStep("WRRBBW", "RB"))
40

1import java.util.Deque;
2import java.util.HashSet;
3import java.util.LinkedList;
4import java.util.Set;
5import java.util.regex.Matcher;
6import java.util.regex.Pattern;
7
8public class Solution {
9    public int findMinStep(String board, String hand) {
10        // Helper function to remove sequences of three or more identical balls
11        String removeConsecutive(String s) {
12            Pattern pattern = Pattern.compile("B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}");
13            Matcher matcher;
14            // Replace sequences of the same ball that are 3 or more in length with empty string
15            do {
16                matcher = pattern.matcher(s);
17                if (!matcher.find())
18                    break;  // If no such sequences are found, stop the loop
19                s = matcher.replaceAll("");
20            } while (true);
21            return s;
22        }
23
24        Set<String> visited = new HashSet<>();  // Set to track visited states to avoid duplicates
25        Deque<Pair<String, String>> queue = new LinkedList<>();  // Queue for BFS with initial states
26
27        queue.offer(new Pair<>(board, hand));  // Queue the initial state
28
29        while (!queue.isEmpty()) {
30            Pair<String, String> currentState = queue.poll();
31            String currentBoard = currentState.getKey();
32            String remainingBalls = currentState.getValue();
33            // If the board is empty, return the number of balls used
34            if (currentBoard.isEmpty()) {
35                return hand.length() - remainingBalls.length();
36            }
37            for (char ball : new HashSet<>(remainingBalls.toCharArray())) {  // Iterate through unique balls
38                String nextBalls = remainingBalls.replaceFirst(String.valueOf(ball), "");  // Remove one ball from the hand
39                for (int i = 0; i <= currentBoard.length(); i++) {
40                    // Insert the ball into every possible position on the board
41                    String newBoard = currentBoard.substring(0, i) + ball + currentBoard.substring(i);
42                    newBoard = removeConsecutive(newBoard);  // Remove consecutive sequences
43                    String newBoardState = newBoard + " " + nextBalls; // Combine newBoard and nextBalls to create a new state
44                    if (!visited.contains(newBoardState)) {
45                        visited.add(newBoardState);   // Mark the new state as visited
46                        queue.offer(new Pair<>(newBoard, nextBalls)); // Queue the new state
47                    }
48                }
49            }
50        }
51
52        return -1;  // Return -1 if no solution is found
53    }
54
55    // Class to hold the pair of board and hand
56    static class Pair<K, V> {
57        private K key;
58        private V value;
59
60        public Pair(K key, V value) {
61            this.key = key;
62            this.value = value;
63        }
64
65        public K getKey() {
66            return key;
67        }
68
69        public V getValue() {
70            return value;
71        }
72    }
73  
74    // Example usage:
75    public static void main(String[] args) {
76        Solution sol = new Solution();
77        System.out.println(sol.findMinStep("WRRBBW", "RB")); // Outputs the minimum step
78    }
79}
80

1#include <string>
2#include <queue>
3#include <unordered_set>
4#include <regex>
5
6using std::string;
7using std::queue;
8using std::unordered_set;
9using std::regex;
10using std::regex_replace;
11
12class Solution {
13public:
14    int findMinStep(string board, string hand) {
15        // Helper function to remove sequences of three or more identical balls
16        auto removeConsecutive = [](const string& s) -> string {
17            string result = s;
18            regex pattern("B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}");
19            while (true) {
20                string nextStr = regex_replace(result, pattern, "");
21                if (nextStr.length() == result.length()) {
22                    break;
23                }
24                result = nextStr;
25            }
26            return result;
27        };
28
29        unordered_set<string> visited; // Set to track visited states to avoid duplicates
30        queue<pair<string, string>> q; // Queue for BFS with initial state
31
32        q.push({board, hand}); // Enqueue initial state
33
34        while (!q.empty()) {
35            string currentBoard; // Current state of the board
36            string remainingBalls; // Remaining balls in hand
37            // Dequeue the next state
38            tie(currentBoard, remainingBalls) = q.front();
39            q.pop();
40
41            // If the board is empty, return the number of balls used
42            if (currentBoard.empty()) {
43                return hand.length() - remainingBalls.length();
44            }
45
46            for (auto &ball: unordered_set<char>(remainingBalls.begin(), remainingBalls.end())) { // Iterate through unique balls
47                string nextBalls = remainingBalls; // Copy remaining balls
48                nextBalls.erase(nextBalls.find(ball), 1); // Remove one occurrence of the ball
49
50                for (size_t i = 0; i <= currentBoard.size(); ++i) {
51                    // Insert the ball into every possible position on the board
52                    string newBoard = currentBoard.substr(0, i) + ball + currentBoard.substr(i);
53                    newBoard = removeConsecutive(newBoard); // Remove consecutive sequences
54
55                    string visitedState = newBoard + " " + nextBalls; // State representation with board and hand
56                    if (!visited.count(visitedState)) { // If this state hasn't been visited yet
57                        visited.insert(visitedState); // Mark the new state as visited
58                        q.push({newBoard, nextBalls}); // Enqueue the new state
59                    }
60                }
61            }
62        }
63
64        return -1; // Return -1 if no solution is found
65    }
66};
67
68// Example usage:
69// Solution sol;
70// std::cout << sol.findMinStep("WRRBBW", "RB") << std::endl;
71

1import { Queue } from 'collections/queue'; // Assume an appropriate Queue implementation is available
2
3// Helper function to remove sequences of three or more identical balls
4const removeConsecutive = (s: string): string => {
5    let nextStr: string;
6    const pattern: RegExp = /(B{3,})|(G{3,})|(R{3,})|(W{3,})|(Y{3,})/g;
7
8    // Use a loop to keep replacing sequences until no more can be found
9    do {
10        // replace sequences of the same ball that are 3 or more in length with empty string
11        nextStr = s.replace(pattern, '');
12        if (nextStr.length === s.length) {
13            break;
14        }
15        s = nextStr;
16    } while(true);
17  
18    return s;
19};
20
21// Typescript does not have built-in set-like structures, assuming use of a Set implementation
22let visited: Set<string> = new Set(); // Set to track visited states to avoid duplicates
23
24// Queue for BFS with initial state, have to initialize with any Queue implementation
25let queue: Queue<[string, string]> = new Queue<[string, string]>();
26
27// Function to find minimum steps to remove all balls from the board
28export const findMinStep = (board: string, hand: string): number => {
29    queued.enqueue([board, hand]);  // Enqueue the initial state
30
31    while (!queue.isEmpty()) {
32        let [currentBoard, remainingBalls]: [string, string] = queue.dequeue();
33
34        // If the board is empty, return the number of balls used
35        if (!currentBoard) {
36            return hand.length - remainingBalls.length;
37        }
38
39        for (let ball of new Set(remainingBalls.split(''))) { // Iterate through unique balls
40            let nextBalls = remainingBalls.replace(ball, ''); // Remove a ball from the hand
41
42            for (let i = 0; i <= currentBoard.length; i++) {
43                // Insert the ball into every possible position on the board
44                let newBoard: string = currentBoard.slice(0, i) + ball + currentBoard.slice(i);
45                newBoard = removeConsecutive(newBoard); // Remove consecutive sequences
46
47                if (!visited.has(newBoard)) {
48                    visited.add(newBoard); // Mark the new board as visited
49                    queue.enqueue([newBoard, nextBalls]); // Enqueue the new state
50                }
51            }
52        }
53    }
54
55    // Return -1 if no solution is found
56    return -1;
57};
58
59// Example usage
60// console.log(findMinStep("WRRBBW", "RB"));
61

Time and Space Complexity

Time Complexity

The given code implements a BFS (Breadth-First Search) to find the minimum number of steps required to remove all balls from the "board" using the balls given in the "hand". The time complexity of the algorithm is dominated by the BFS and the remove() function that is called repeatedly within the BFS loop.

BFS: In the worst case, we try adding each ball from the hand to every possible position in the board. If there are n positions in the board and m balls in the hand, then for every state there could be up to n * m new states added to the queue. In the worst case, this can happen repeatedly for every state.
remove() Function: The remove() function uses a regular expression to repeatedly remove series of 3 or more adjacent balls of the same color until no more such series exist. In the worst case, every removal might only remove 3 balls from a sequence of many adjacent balls of the same color, potentially leading to a linear number of regular expression applications proportional to the length of the sequence.

If k is the maximum length of the board at any state, then the time complexity for remove() is O(k^2) since re.sub() has a complexity of O(k) and it may be called k times in the worst case.

As a result, the overall worst-case time complexity of the code can be expressed as O((n*m)^k * k^2).

Space Complexity

For space complexity, the considerations are:

Queue: The queue can hold at most O((n*m)^k) elements, where each element consists of a board state and the remaining hand.
Visited Set: The visited set holds the unique board configurations. In the worst case, it will hold the same number of elements as there are in the queue, which is O((n*m)^k).

Thus, the space complexity of the algorithm is O((n*m)^k) due to the queue and the visited states.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know