488. Zuma Game
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 there.sub
method from there
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 inhand
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 EvaluatorExample 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 handRB
. -
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 inWBBW
. - Insert 'R' at the end. New board
WRRBBWR
. No removal is triggered since we don't have three 'R's in a row.
- Insert 'R' between 'W' and 'RR'. New board would be
-
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 ofB
. -
Removals and State Updates: We continue with state
WBBW
and handB
. We insert 'B' between 'BB', and the new board isWBBBBW
. This triggers a removal, clearing all 'B's and resulting inWW
.- After removal, the board is
WW
, and the hand is empty.
- After removal, the board is
-
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 andm
balls in the hand, then for every state there could be up ton * 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.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again