488. Zuma Game
Problem Description
This problem is based on a variation of the game Zuma where you need to clear all colored balls from a board.
You have:
- A board represented as a string containing a row of colored balls, where each ball can be one of five colors: Red ('R'), Yellow ('Y'), Blue ('B'), Green ('G'), or White ('W')
- A hand represented as a string containing balls you can insert into the board
The game mechanics work as follows:
-
Insert Phase: On each turn, you pick any ball from your hand and insert it at any position in the board (between any two balls or at either end)
-
Removal Phase: After insertion, if there are three or more consecutive balls of the same color, they are automatically removed from the board. This removal can trigger a chain reaction - if removing a group causes another group of three or more same-colored balls to become adjacent, those are removed too. This continues until no more groups can be removed.
-
Win Condition: You win when the board becomes empty (all balls cleared)
-
Game Continuation: Keep inserting balls from your hand until either:
- You clear the board (win), or
- You run out of balls in your hand but the board still has balls (lose)
The task is to find the minimum number of balls you need to insert from your hand to clear the entire board. If it's impossible to clear the board with the balls you have, return -1.
For example:
- Board:
"WRRBBW", Hand:"RB" - You could insert 'R' between the two existing R's to make
"WRRRBW", which removes the three R's, leaving"WBBW" - Then insert 'B' to make
"WBBBW", which removes the three B's, leaving"WW" - The board still has balls but you're out of moves, so more insertions would be needed
The solution uses BFS to explore all possible insertion positions and ball choices, tracking visited board states to avoid repetition, and automatically removing groups of three or more same-colored balls after each insertion using regex pattern matching.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: This problem can be modeled as a graph where each state (board configuration + remaining balls in hand) is a node, and edges represent valid moves (inserting a ball from hand into the board).
Is it a tree?
- No: The state space is not a tree because different sequences of moves can lead to the same board state (multiple paths to the same node).
Is the problem related to directed acyclic graphs?
- No: The problem is not specifically about DAGs or topological ordering.
Is the problem related to shortest paths?
- Yes: We need to find the minimum number of balls to insert (minimum number of moves) to clear the board, which is essentially finding the shortest path from the initial state to an empty board state.
Is the graph Weighted?
- No: Each move (inserting one ball) has the same cost of 1, making this an unweighted graph problem.
BFS
- Yes: For unweighted shortest path problems, BFS is the optimal choice.
Conclusion: The flowchart suggests using BFS (Breadth-First Search) for this problem. BFS is perfect here because:
- We're exploring a state space where each state is a (board, hand) configuration
- We need the minimum number of moves (shortest path in an unweighted graph)
- BFS guarantees finding the optimal solution by exploring states level by level
- The solution uses a queue to process states and a visited set to avoid revisiting the same board configurations
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?
Intuition
The key insight is to think of this problem as exploring different game states to find the optimal sequence of moves. Each state represents a snapshot of the game: what balls are on the board and what balls remain in your hand.
Starting from the initial state, we want to try all possible moves and see which path leads to an empty board with the fewest insertions. This naturally suggests a state-space search problem.
Why BFS over other approaches? Consider these observations:
-
Each move has equal cost: Inserting any ball costs exactly 1 move, regardless of which ball or where we insert it. This makes it an unweighted graph problem.
-
We need the minimum: Among all possible ways to clear the board, we want the one using the fewest balls. BFS explores states level by level, guaranteeing that the first time we reach the winning state (empty board), we've used the minimum number of moves.
-
State representation matters: A state is uniquely defined by the current board configuration and remaining balls in hand. However, we can optimize by only tracking visited board states (not the hand), since if we've seen a board configuration before, we've already explored the optimal ways to clear it.
The chain reaction mechanism (removing groups of 3+ same-colored balls repeatedly) is handled by a helper function remove() that simulates the cascading removals after each insertion. This is crucial because one strategic insertion might trigger multiple removals, dramatically changing the board state.
The algorithm systematically tries:
- Each unique ball color from our hand (no need to try duplicate balls of the same color in the same round)
- Each possible insertion position on the board
- Applies the removal rules to get the resulting board state
- Continues exploration if this board state hasn't been visited before
By using BFS with this state exploration strategy, we ensure finding the shortest path (minimum insertions) from the initial state to the victory condition (empty board), or determine it's impossible if no such path exists.
Solution Approach
The solution implements BFS using a queue and a visited set to track explored board states. Let's walk through the implementation details:
1. Chain Removal Function (remove)
The helper function handles the cascading removal of consecutive balls:
def remove(s):
while len(s):
next = re.sub(r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}', '', s)
if len(next) == len(s):
break
s = next
return s
- Uses regex to find and remove groups of 3 or more consecutive same-colored balls
- The pattern
r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}'matches 3+ consecutive occurrences of any color - Continues removing until no more groups can be removed (when string length stops changing)
2. BFS Initialization
visited = set()
q = deque([(board, hand)])
visited: Set to track board states we've already explored (prevents infinite loops)q: Queue storing tuples of(current_board_state, remaining_balls_in_hand)- Starts with the initial board and full hand
3. BFS Main Loop
while q:
state, balls = q.popleft()
if not state:
return len(hand) - len(balls)
- Dequeues states in FIFO order (ensuring level-by-level exploration)
- If we reach an empty board (
not state), we've won! - Returns the number of balls used:
len(hand) - len(balls)
4. Move Generation and Exploration
for ball in set(balls):
b = balls.replace(ball, '', 1)
for i in range(1, len(state) + 1):
s = state[:i] + ball + state[i:]
s = remove(s)
if s not in visited:
visited.add(s)
q.append((s, b))
This nested loop structure generates all possible moves:
- Outer loop: Iterates through unique ball colors in hand using
set(balls)balls.replace(ball, '', 1)removes exactly one instance of the chosen ball
- Inner loop: Tries inserting the ball at every position (0 to len(state))
state[:i] + ball + state[i:]inserts the ball at positioni- Applies
remove()to handle chain reactions - If the resulting board state is new, adds it to visited and enqueues for exploration
5. Termination
return -1
If the queue empties without finding an empty board state, it's impossible to clear the board with the given hand.
Key Optimizations:
- Using
set(balls)avoids redundant attempts with duplicate balls in the same round - Tracking only board states (not hand states) in
visitedreduces memory usage - The regex-based removal is efficient for pattern matching and replacement
The algorithm explores O(n! × m^n) states in the worst case, where n is hand size and m is board positions, but the visited set pruning significantly reduces actual exploration.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's trace through a small example to see how the BFS solution works:
Initial State:
- Board:
"RBYYBBR" - Hand:
"YRBR"
Goal: Clear the board using minimum insertions.
BFS Exploration:
Round 1 (Initial state):
- Queue:
[("RBYYBBR", "YRBR")] - We explore all possible first moves
Let's trace one promising path:
Option 1A: Insert 'Y' at position 3
- Take 'Y' from hand → Remaining hand:
"RBR" - Insert at position 3:
"RBY|Y|YBBR"→"RBYYYBBR" - Apply remove():
"RBYYYBBR"→"RBBBR"(3 Y's removed) - Apply remove() again:
"RBBBR"→"RR"(3 B's removed!) - New state:
("RR", "RBR") - This triggers a chain reaction removing 6 balls with just 1 insertion!
Round 2 (From state "RR"):
- Current board:
"RR" - Remaining hand:
"RBR" - Try inserting 'R' between the two R's:
- Insert at position 1:
"R|R|R"→"RRR" - Apply remove():
"RRR"→""(3 R's removed) - Board is empty! Victory!
- Insert at position 1:
Result: Minimum insertions = 2
Why BFS finds this optimal solution:
-
Level 1 exploration: BFS tries all possible first insertions:
- Insert each unique ball ('Y', 'R', 'B') at each position (0-7)
- Many paths lead nowhere productive
- The path inserting 'Y' at position 3 creates the chain reaction
-
Level 2 exploration: From each resulting state, try all second insertions:
- The state
"RR"reached by our path needs only one more move - Other paths might still have longer boards requiring more moves
- The state
-
First success = optimal: Since BFS explores level-by-level, finding an empty board at level 2 guarantees no solution exists using fewer insertions.
Key observations from this example:
- Strategic placement matters: Inserting 'Y' at position 3 (not 2 or 4) triggers the optimal chain
- Chain reactions are powerful: One insertion removed 6 balls
- The visited set prevents re-exploring
"RR"if other paths reach it later - Using
set(balls)in Round 1 means we only try 'Y', 'R', 'B' once each (not 'R' twice)
Solution Implementation
1import re
2from collections import deque
3
4class Solution:
5 def findMinStep(self, board: str, hand: str) -> int:
6 def remove_consecutive_balls(board_state):
7 """
8 Remove groups of 3 or more consecutive same-colored balls.
9 Keep removing until no more groups can be removed.
10 """
11 while board_state:
12 # Remove any sequence of 3 or more consecutive same-colored balls
13 new_board = re.sub(r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}', '', board_state)
14
15 # If nothing was removed, we're done
16 if len(new_board) == len(board_state):
17 break
18
19 board_state = new_board
20
21 return board_state
22
23 # Track visited board states to avoid revisiting
24 visited_states = set()
25
26 # BFS queue: each element is (current_board_state, remaining_balls_in_hand)
27 queue = deque([(board, hand)])
28
29 while queue:
30 current_board, remaining_balls = queue.popleft()
31
32 # If board is empty, we've won - return number of balls used
33 if not current_board:
34 return len(hand) - len(remaining_balls)
35
36 # Try each unique ball color in our hand
37 for ball_color in set(remaining_balls):
38 # Remove one ball of this color from hand
39 new_hand = remaining_balls.replace(ball_color, '', 1)
40
41 # Try inserting the ball at each position in the board (including after last position)
42 for insert_position in range(len(current_board) + 1):
43 # Insert ball at current position
44 new_board = current_board[:insert_position] + ball_color + current_board[insert_position:]
45
46 # Remove any groups of 3+ consecutive balls
47 new_board = remove_consecutive_balls(new_board)
48
49 # If we haven't seen this board state before, explore it
50 if new_board not in visited_states:
51 visited_states.add(new_board)
52 queue.append((new_board, new_hand))
53
54 # If we exhausted all possibilities without clearing the board, return -1
55 return -1
561class Solution {
2 /**
3 * Find minimum steps to clear the board by inserting balls from hand
4 * @param board Initial board state string
5 * @param hand Available balls in hand string
6 * @return Minimum steps to clear board, or -1 if impossible
7 */
8 public int findMinStep(String board, String hand) {
9 // Create initial Zuma game state
10 final Zuma zuma = Zuma.create(board, hand);
11 // Track visited states to avoid cycles
12 final HashSet<Long> visited = new HashSet<>();
13 // Initialize BFS queue with starting state
14 final ArrayList<Zuma> initialStates = new ArrayList<>();
15
16 visited.add(zuma.board());
17 initialStates.add(zuma);
18 return bfs(initialStates, 0, visited);
19 }
20
21 /**
22 * Breadth-first search to find minimum steps
23 * @param currentLevel Current level states to explore
24 * @param depth Current depth/steps taken
25 * @param visited Set of visited board states
26 * @return Minimum steps to solution or -1 if no solution
27 */
28 private int bfs(ArrayList<Zuma> currentLevel, int depth, HashSet<Long> visited) {
29 // No more states to explore - no solution found
30 if (currentLevel.isEmpty()) {
31 return -1;
32 }
33
34 // Prepare next level for BFS
35 final ArrayList<Zuma> nextLevel = new ArrayList<>();
36
37 // Explore all states at current level
38 for (Zuma zuma : currentLevel) {
39 ArrayList<Zuma> neighbors = zuma.getNextLevel(depth, visited);
40 // null indicates board was cleared - solution found
41 if (neighbors == null) {
42 return depth + 1;
43 }
44 nextLevel.addAll(neighbors);
45 }
46
47 // Continue BFS with next level
48 return bfs(nextLevel, depth + 1, visited);
49 }
50}
51
52/**
53 * Record representing the Zuma game state
54 * Encodes board and hand as bit-packed longs for efficient operations
55 */
56record Zuma(long board, long hand) {
57 /**
58 * Factory method to create Zuma from string representations
59 * @param boardStr Board configuration string
60 * @param handStr Hand configuration string
61 * @return New Zuma instance with encoded states
62 */
63 public static Zuma create(String boardStr, String handStr) {
64 return new Zuma(
65 Zuma.encode(boardStr, false), // Board maintains order
66 Zuma.encode(handStr, true) // Hand is sorted for consistency
67 );
68 }
69
70 /**
71 * Generate all valid next states from current state
72 * @param depth Current search depth for pruning
73 * @param visited Set of visited states to avoid revisiting
74 * @return List of next states, or null if board cleared
75 */
76 public ArrayList<Zuma> getNextLevel(int depth, HashSet<Long> visited) {
77 final ArrayList<Zuma> nextStates = new ArrayList<>();
78 // Get unique balls from hand
79 final ArrayList<long[]> handOptions = this.buildHandList();
80 // Get all possible insertion positions on board
81 final long[] boardPositions = new long[32];
82 final int numPositions = this.buildBoardList(boardPositions);
83
84 // Try each ball type from hand
85 for (long[] ballAndRemainingHand : handOptions) {
86 // Try inserting at each position on board
87 for (int position = 0; position < numPositions; ++position) {
88 // Check if this insertion is worth exploring (pruning)
89 final long boardAfterInsertion = pruningCheck(
90 boardPositions[position],
91 ballAndRemainingHand[0],
92 position * 3,
93 depth
94 );
95
96 if (boardAfterInsertion == -1) {
97 continue; // Skip this insertion
98 }
99
100 // Apply elimination rules to get final board state
101 final long updatedBoard = updateBoard(boardAfterInsertion);
102
103 // Board cleared - solution found
104 if (updatedBoard == 0) {
105 return null;
106 }
107
108 // Skip if no balls left or state already visited
109 if (ballAndRemainingHand[1] == 0 || visited.contains(updatedBoard)) {
110 continue;
111 }
112
113 // Add new valid state
114 visited.add(updatedBoard);
115 nextStates.add(new Zuma(updatedBoard, ballAndRemainingHand[1]));
116 }
117 }
118 return nextStates;
119 }
120
121 /**
122 * Pruning heuristic to avoid unnecessary insertions
123 * @param insertionBoard Board with space for insertion
124 * @param ball Ball to insert (3 bits)
125 * @param position Bit position for insertion
126 * @param depth Current search depth
127 * @return Board after insertion or -1 if pruned
128 */
129 private long pruningCheck(long insertionBoard, long ball, int position, int depth) {
130 // Extract left and right neighbors at insertion point
131 final long leftNeighbor = (insertionBoard >> (position + 3)) & 0x7;
132 final long rightNeighbor = (insertionBoard >> (position - 3)) & 0x7;
133
134 // Pruning rules based on depth and neighbor colors
135 if (depth == 0 && (ball != rightNeighbor) && (leftNeighbor != rightNeighbor)
136 || depth > 0 && (ball != rightNeighbor)) {
137 return -1; // Prune this insertion
138 }
139
140 // Return board with ball inserted at position
141 return insertionBoard | (ball << position);
142 }
143
144 /**
145 * Apply elimination rules to board after insertion
146 * Uses stack-based approach to handle consecutive same-colored balls
147 * @param board Board state after insertion
148 * @return Updated board after eliminations
149 */
150 private long updateBoard(long board) {
151 long stack = 0; // Stack to track balls and handle eliminations
152
153 // Process each 3-bit ball from right to left
154 for (int bitPosition = 0; bitPosition < 64; bitPosition += 3) {
155 final long currentBall = (board >> bitPosition) & 0x7;
156 final long topBall = stack & 0x7;
157
158 // Check if we can eliminate balls (3+ consecutive same color)
159 if ((topBall > 0) && (currentBall != topBall) &&
160 (stack & 0x3F) == ((stack >> 3) & 0x3F)) {
161 // Remove 3 consecutive balls
162 stack >>= 9;
163 // Check if 4th ball is also same color
164 if ((stack & 0x7) == topBall) {
165 stack >>= 3; // Remove 4th ball too
166 }
167 }
168
169 // End of board reached
170 if (currentBall == 0) {
171 break;
172 }
173
174 // Push current ball onto stack
175 stack = (stack << 3) | currentBall;
176 }
177 return stack;
178 }
179
180 /**
181 * Build list of unique balls from hand with remaining hand state
182 * @return List of [ball_type, remaining_hand] pairs
183 */
184 private ArrayList<long[]> buildHandList() {
185 final ArrayList<long[]> handList = new ArrayList<>();
186 long previousBall = 0;
187 long ballMask = 0;
188
189 // Process each 3-bit ball in hand
190 for (int bitPosition = 0; bitPosition < 16; bitPosition += 3) {
191 final long currentBall = (this.hand >> bitPosition) & 0x7;
192
193 // End of hand reached
194 if (currentBall == 0) {
195 break;
196 }
197
198 // Add only unique ball types (hand is sorted)
199 if (currentBall != previousBall) {
200 previousBall = currentBall;
201 // Create pair: [ball_type, hand_without_this_ball]
202 handList.add(new long[] {
203 currentBall,
204 ((this.hand >> 3) & ~ballMask) | (this.hand & ballMask)
205 });
206 }
207 ballMask = (ballMask << 3) | 0x7;
208 }
209 return handList;
210 }
211
212 /**
213 * Build list of all possible board configurations with insertion points
214 * @param buffer Array to store board configurations
215 * @return Number of valid insertion positions
216 */
217 private int buildBoardList(long[] buffer) {
218 int bufferIndex = 0;
219 long ballMask = 0x7;
220 // Create space at beginning for insertion
221 long insertionBoard = this.board << 3;
222 buffer[bufferIndex++] = insertionBoard;
223
224 // Generate board with insertion point at each position
225 while (true) {
226 final long currentBall = this.board & ballMask;
227
228 // End of board reached
229 if (currentBall == 0) {
230 break;
231 }
232
233 ballMask <<= 3;
234 // Move ball and create space for next insertion
235 insertionBoard = (insertionBoard | currentBall) & ~ballMask;
236 buffer[bufferIndex++] = insertionBoard;
237 }
238 return bufferIndex;
239 }
240
241 /**
242 * Encode string state into bit-packed long
243 * @param stateStr String representation of state
244 * @param sortFlag Whether to sort characters before encoding
245 * @return Encoded state as long (3 bits per ball)
246 */
247 private static long encode(String stateStr, boolean sortFlag) {
248 final char[] stateChars = stateStr.toCharArray();
249
250 // Sort for consistent hand representation
251 if (sortFlag) {
252 Arrays.sort(stateChars);
253 }
254
255 long encodedBits = 0;
256 // Pack each character as 3 bits
257 for (char ch : stateChars) {
258 encodedBits = (encodedBits << 3) | Zuma.encode(ch);
259 }
260 return encodedBits;
261 }
262
263 /**
264 * Encode single character to 3-bit representation
265 * @param ch Character representing ball color
266 * @return 3-bit encoded value
267 */
268 private static long encode(char ch) {
269 return switch (ch) {
270 case 'R' -> 0x1; // Red
271 case 'G' -> 0x2; // Green
272 case 'B' -> 0x3; // Blue
273 case 'W' -> 0x4; // White
274 case 'Y' -> 0x5; // Yellow
275 case ' ' -> 0x0; // Empty/delimiter
276 default -> throw new IllegalArgumentException("Invalid char: " + ch);
277 };
278 }
279}
2801#include <vector>
2#include <unordered_set>
3#include <algorithm>
4#include <string>
5#include <stdexcept>
6
7using namespace std;
8
9class Zuma {
10private:
11 long long board;
12 long long hand;
13
14public:
15 /**
16 * Constructor for Zuma game state
17 * @param board_val Encoded board state
18 * @param hand_val Encoded hand state
19 */
20 Zuma(long long board_val, long long hand_val) : board(board_val), hand(hand_val) {}
21
22 /**
23 * Get board state
24 * @return Encoded board value
25 */
26 long long getBoard() const { return board; }
27
28 /**
29 * Get hand state
30 * @return Encoded hand value
31 */
32 long long getHand() const { return hand; }
33
34 /**
35 * Factory method to create Zuma from string representations
36 * @param board_str Board configuration string
37 * @param hand_str Hand configuration string
38 * @return New Zuma instance with encoded states
39 */
40 static Zuma create(const string& board_str, const string& hand_str) {
41 return Zuma(
42 encode(board_str, false), // Board maintains order
43 encode(hand_str, true) // Hand is sorted for consistency
44 );
45 }
46
47 /**
48 * Generate all valid next states from current state
49 * @param depth Current search depth for pruning
50 * @param visited Set of visited states to avoid revisiting
51 * @return Pointer to list of next states, or nullptr if board cleared
52 */
53 vector<Zuma>* getNextLevel(int depth, unordered_set<long long>& visited) {
54 vector<Zuma>* next_states = new vector<Zuma>();
55
56 // Get unique balls from hand
57 vector<pair<long long, long long>> hand_options = buildHandList();
58
59 // Get all possible insertion positions on board
60 vector<long long> board_positions(32);
61 int num_positions = buildBoardList(board_positions);
62
63 // Try each ball type from hand
64 for (const auto& ball_and_remaining : hand_options) {
65 long long ball = ball_and_remaining.first;
66 long long remaining_hand = ball_and_remaining.second;
67
68 // Try inserting at each position on board
69 for (int position = 0; position < num_positions; ++position) {
70 // Check if this insertion is worth exploring (pruning)
71 long long board_after_insertion = pruningCheck(
72 board_positions[position],
73 ball,
74 position * 3,
75 depth
76 );
77
78 if (board_after_insertion == -1) {
79 continue; // Skip this insertion
80 }
81
82 // Apply elimination rules to get final board state
83 long long updated_board = updateBoard(board_after_insertion);
84
85 // Board cleared - solution found
86 if (updated_board == 0) {
87 delete next_states;
88 return nullptr;
89 }
90
91 // Skip if no balls left or state already visited
92 if (remaining_hand == 0 || visited.count(updated_board) > 0) {
93 continue;
94 }
95
96 // Add new valid state
97 visited.insert(updated_board);
98 next_states->push_back(Zuma(updated_board, remaining_hand));
99 }
100 }
101
102 return next_states;
103 }
104
105private:
106 /**
107 * Pruning heuristic to avoid unnecessary insertions
108 * @param insertion_board Board with space for insertion
109 * @param ball Ball to insert (3 bits)
110 * @param position Bit position for insertion
111 * @param depth Current search depth
112 * @return Board after insertion or -1 if pruned
113 */
114 long long pruningCheck(long long insertion_board, long long ball, int position, int depth) {
115 // Extract left and right neighbors at insertion point
116 long long left_neighbor = (insertion_board >> (position + 3)) & 0x7;
117 long long right_neighbor = (insertion_board >> (position - 3)) & 0x7;
118
119 // Pruning rules based on depth and neighbor colors
120 if ((depth == 0 && ball != right_neighbor && left_neighbor != right_neighbor) ||
121 (depth > 0 && ball != right_neighbor)) {
122 return -1; // Prune this insertion
123 }
124
125 // Return board with ball inserted at position
126 return insertion_board | (ball << position);
127 }
128
129 /**
130 * Apply elimination rules to board after insertion
131 * Uses stack-based approach to handle consecutive same-colored balls
132 * @param board Board state after insertion
133 * @return Updated board after eliminations
134 */
135 long long updateBoard(long long board) {
136 long long stack = 0; // Stack to track balls and handle eliminations
137
138 // Process each 3-bit ball from right to left
139 for (int bit_position = 0; bit_position < 64; bit_position += 3) {
140 long long current_ball = (board >> bit_position) & 0x7;
141 long long top_ball = stack & 0x7;
142
143 // Check if we can eliminate balls (3+ consecutive same color)
144 if (top_ball > 0 && current_ball != top_ball &&
145 (stack & 0x3F) == ((stack >> 3) & 0x3F)) {
146 // Remove 3 consecutive balls
147 stack >>= 9;
148 // Check if 4th ball is also same color
149 if ((stack & 0x7) == top_ball) {
150 stack >>= 3; // Remove 4th ball too
151 }
152 }
153
154 // End of board reached
155 if (current_ball == 0) {
156 break;
157 }
158
159 // Push current ball onto stack
160 stack = (stack << 3) | current_ball;
161 }
162
163 return stack;
164 }
165
166 /**
167 * Build list of unique balls from hand with remaining hand state
168 * @return List of [ball_type, remaining_hand] pairs
169 */
170 vector<pair<long long, long long>> buildHandList() {
171 vector<pair<long long, long long>> hand_list;
172 long long previous_ball = 0;
173 long long ball_mask = 0;
174
175 // Process each 3-bit ball in hand
176 for (int bit_position = 0; bit_position < 16; bit_position += 3) {
177 long long current_ball = (hand >> bit_position) & 0x7;
178
179 // End of hand reached
180 if (current_ball == 0) {
181 break;
182 }
183
184 // Add only unique ball types (hand is sorted)
185 if (current_ball != previous_ball) {
186 previous_ball = current_ball;
187 // Create pair: [ball_type, hand_without_this_ball]
188 long long remaining = ((hand >> 3) & ~ball_mask) | (hand & ball_mask);
189 hand_list.push_back({current_ball, remaining});
190 }
191
192 ball_mask = (ball_mask << 3) | 0x7;
193 }
194
195 return hand_list;
196 }
197
198 /**
199 * Build list of all possible board configurations with insertion points
200 * @param buffer Array to store board configurations
201 * @return Number of valid insertion positions
202 */
203 int buildBoardList(vector<long long>& buffer) {
204 int buffer_index = 0;
205 long long ball_mask = 0x7;
206
207 // Create space at beginning for insertion
208 long long insertion_board = board << 3;
209 buffer[buffer_index++] = insertion_board;
210
211 // Generate board with insertion point at each position
212 while (true) {
213 long long current_ball = board & ball_mask;
214
215 // End of board reached
216 if (current_ball == 0) {
217 break;
218 }
219
220 ball_mask <<= 3;
221 // Move ball and create space for next insertion
222 insertion_board = (insertion_board | current_ball) & ~ball_mask;
223 buffer[buffer_index++] = insertion_board;
224 }
225
226 return buffer_index;
227 }
228
229 /**
230 * Encode string state into bit-packed long
231 * @param state_str String representation of state
232 * @param sort_flag Whether to sort characters before encoding
233 * @return Encoded state as long (3 bits per ball)
234 */
235 static long long encode(string state_str, bool sort_flag) {
236 // Sort for consistent hand representation
237 if (sort_flag) {
238 sort(state_str.begin(), state_str.end());
239 }
240
241 long long encoded_bits = 0;
242
243 // Pack each character as 3 bits
244 for (char ch : state_str) {
245 encoded_bits = (encoded_bits << 3) | encodeChar(ch);
246 }
247
248 return encoded_bits;
249 }
250
251 /**
252 * Encode single character to 3-bit representation
253 * @param ch Character representing ball color
254 * @return 3-bit encoded value
255 */
256 static long long encodeChar(char ch) {
257 switch (ch) {
258 case 'R': return 0x1; // Red
259 case 'G': return 0x2; // Green
260 case 'B': return 0x3; // Blue
261 case 'W': return 0x4; // White
262 case 'Y': return 0x5; // Yellow
263 case ' ': return 0x0; // Empty/delimiter
264 default: throw invalid_argument("Invalid char: " + string(1, ch));
265 }
266 }
267};
268
269class Solution {
270public:
271 /**
272 * Find minimum steps to clear the board by inserting balls from hand
273 * @param board Initial board state string
274 * @param hand Available balls in hand string
275 * @return Minimum steps to clear board, or -1 if impossible
276 */
277 int findMinStep(string board, string hand) {
278 // Create initial Zuma game state
279 Zuma zuma = Zuma::create(board, hand);
280
281 // Track visited states to avoid cycles
282 unordered_set<long long> visited;
283
284 // Initialize BFS queue with starting state
285 vector<Zuma> initial_states;
286
287 visited.insert(zuma.getBoard());
288 initial_states.push_back(zuma);
289
290 return bfs(initial_states, 0, visited);
291 }
292
293private:
294 /**
295 * Breadth-first search to find minimum steps
296 * @param current_level Current level states to explore
297 * @param depth Current depth/steps taken
298 * @param visited Set of visited board states
299 * @return Minimum steps to solution or -1 if no solution
300 */
301 int bfs(vector<Zuma> current_level, int depth, unordered_set<long long>& visited) {
302 // No more states to explore - no solution found
303 if (current_level.empty()) {
304 return -1;
305 }
306
307 // Prepare next level for BFS
308 vector<Zuma> next_level;
309
310 // Explore all states at current level
311 for (Zuma& zuma : current_level) {
312 vector<Zuma>* neighbors = zuma.getNextLevel(depth, visited);
313
314 // nullptr indicates board was cleared - solution found
315 if (neighbors == nullptr) {
316 return depth + 1;
317 }
318
319 // Add all neighbors to next level
320 for (const Zuma& neighbor : *neighbors) {
321 next_level.push_back(neighbor);
322 }
323
324 delete neighbors;
325 }
326
327 // Continue BFS with next level
328 return bfs(next_level, depth + 1, visited);
329 }
330};
3311/**
2 * Find minimum steps to clear the board by inserting balls from hand
3 * @param board Initial board state string
4 * @param hand Available balls in hand string
5 * @return Minimum steps to clear board, or -1 if impossible
6 */
7function findMinStep(board: string, hand: string): number {
8 // Create initial Zuma game state
9 const zuma = createZuma(board, hand);
10 // Track visited states to avoid cycles
11 const visited = new Set<bigint>();
12 // Initialize BFS queue with starting state
13 const initialStates: Zuma[] = [];
14
15 visited.add(zuma.board);
16 initialStates.push(zuma);
17 return bfs(initialStates, 0, visited);
18}
19
20/**
21 * Breadth-first search to find minimum steps
22 * @param currentLevel Current level states to explore
23 * @param depth Current depth/steps taken
24 * @param visited Set of visited board states
25 * @return Minimum steps to solution or -1 if no solution
26 */
27function bfs(currentLevel: Zuma[], depth: number, visited: Set<bigint>): number {
28 // No more states to explore - no solution found
29 if (currentLevel.length === 0) {
30 return -1;
31 }
32
33 // Prepare next level for BFS
34 const nextLevel: Zuma[] = [];
35
36 // Explore all states at current level
37 for (const zuma of currentLevel) {
38 const neighbors = getNextLevel(zuma, depth, visited);
39 // null indicates board was cleared - solution found
40 if (neighbors === null) {
41 return depth + 1;
42 }
43 nextLevel.push(...neighbors);
44 }
45
46 // Continue BFS with next level
47 return bfs(nextLevel, depth + 1, visited);
48}
49
50/**
51 * Interface representing the Zuma game state
52 * Encodes board and hand as bit-packed bigints for efficient operations
53 */
54interface Zuma {
55 board: bigint;
56 hand: bigint;
57}
58
59/**
60 * Factory method to create Zuma from string representations
61 * @param boardStr Board configuration string
62 * @param handStr Hand configuration string
63 * @return New Zuma instance with encoded states
64 */
65function createZuma(boardStr: string, handStr: string): Zuma {
66 return {
67 board: encode(boardStr, false), // Board maintains order
68 hand: encode(handStr, true) // Hand is sorted for consistency
69 };
70}
71
72/**
73 * Generate all valid next states from current state
74 * @param zuma Current game state
75 * @param depth Current search depth for pruning
76 * @param visited Set of visited states to avoid revisiting
77 * @return List of next states, or null if board cleared
78 */
79function getNextLevel(zuma: Zuma, depth: number, visited: Set<bigint>): Zuma[] | null {
80 const nextStates: Zuma[] = [];
81 // Get unique balls from hand
82 const handOptions = buildHandList(zuma);
83 // Get all possible insertion positions on board
84 const boardPositions: bigint[] = new Array(32);
85 const numPositions = buildBoardList(zuma, boardPositions);
86
87 // Try each ball type from hand
88 for (const ballAndRemainingHand of handOptions) {
89 // Try inserting at each position on board
90 for (let position = 0; position < numPositions; position++) {
91 // Check if this insertion is worth exploring (pruning)
92 const boardAfterInsertion = pruningCheck(
93 boardPositions[position],
94 ballAndRemainingHand[0],
95 position * 3,
96 depth
97 );
98
99 if (boardAfterInsertion === -1n) {
100 continue; // Skip this insertion
101 }
102
103 // Apply elimination rules to get final board state
104 const updatedBoard = updateBoard(boardAfterInsertion);
105
106 // Board cleared - solution found
107 if (updatedBoard === 0n) {
108 return null;
109 }
110
111 // Skip if no balls left or state already visited
112 if (ballAndRemainingHand[1] === 0n || visited.has(updatedBoard)) {
113 continue;
114 }
115
116 // Add new valid state
117 visited.add(updatedBoard);
118 nextStates.push({ board: updatedBoard, hand: ballAndRemainingHand[1] });
119 }
120 }
121 return nextStates;
122}
123
124/**
125 * Pruning heuristic to avoid unnecessary insertions
126 * @param insertionBoard Board with space for insertion
127 * @param ball Ball to insert (3 bits)
128 * @param position Bit position for insertion
129 * @param depth Current search depth
130 * @return Board after insertion or -1 if pruned
131 */
132function pruningCheck(insertionBoard: bigint, ball: bigint, position: number, depth: number): bigint {
133 // Extract left and right neighbors at insertion point
134 const leftNeighbor = (insertionBoard >> BigInt(position + 3)) & 0x7n;
135 const rightNeighbor = (insertionBoard >> BigInt(position - 3)) & 0x7n;
136
137 // Pruning rules based on depth and neighbor colors
138 if ((depth === 0 && ball !== rightNeighbor && leftNeighbor !== rightNeighbor) ||
139 (depth > 0 && ball !== rightNeighbor)) {
140 return -1n; // Prune this insertion
141 }
142
143 // Return board with ball inserted at position
144 return insertionBoard | (ball << BigInt(position));
145}
146
147/**
148 * Apply elimination rules to board after insertion
149 * Uses stack-based approach to handle consecutive same-colored balls
150 * @param board Board state after insertion
151 * @return Updated board after eliminations
152 */
153function updateBoard(board: bigint): bigint {
154 let stack = 0n; // Stack to track balls and handle eliminations
155
156 // Process each 3-bit ball from right to left
157 for (let bitPosition = 0; bitPosition < 64; bitPosition += 3) {
158 const currentBall = (board >> BigInt(bitPosition)) & 0x7n;
159 const topBall = stack & 0x7n;
160
161 // Check if we can eliminate balls (3+ consecutive same color)
162 if (topBall > 0n && currentBall !== topBall &&
163 (stack & 0x3Fn) === ((stack >> 3n) & 0x3Fn)) {
164 // Remove 3 consecutive balls
165 stack >>= 9n;
166 // Check if 4th ball is also same color
167 if ((stack & 0x7n) === topBall) {
168 stack >>= 3n; // Remove 4th ball too
169 }
170 }
171
172 // End of board reached
173 if (currentBall === 0n) {
174 break;
175 }
176
177 // Push current ball onto stack
178 stack = (stack << 3n) | currentBall;
179 }
180 return stack;
181}
182
183/**
184 * Build list of unique balls from hand with remaining hand state
185 * @param zuma Current game state
186 * @return List of [ball_type, remaining_hand] pairs
187 */
188function buildHandList(zuma: Zuma): [bigint, bigint][] {
189 const handList: [bigint, bigint][] = [];
190 let previousBall = 0n;
191 let ballMask = 0n;
192
193 // Process each 3-bit ball in hand
194 for (let bitPosition = 0; bitPosition < 16; bitPosition += 3) {
195 const currentBall = (zuma.hand >> BigInt(bitPosition)) & 0x7n;
196
197 // End of hand reached
198 if (currentBall === 0n) {
199 break;
200 }
201
202 // Add only unique ball types (hand is sorted)
203 if (currentBall !== previousBall) {
204 previousBall = currentBall;
205 // Create pair: [ball_type, hand_without_this_ball]
206 handList.push([
207 currentBall,
208 ((zuma.hand >> 3n) & ~ballMask) | (zuma.hand & ballMask)
209 ]);
210 }
211 ballMask = (ballMask << 3n) | 0x7n;
212 }
213 return handList;
214}
215
216/**
217 * Build list of all possible board configurations with insertion points
218 * @param zuma Current game state
219 * @param buffer Array to store board configurations
220 * @return Number of valid insertion positions
221 */
222function buildBoardList(zuma: Zuma, buffer: bigint[]): number {
223 let bufferIndex = 0;
224 let ballMask = 0x7n;
225 // Create space at beginning for insertion
226 let insertionBoard = zuma.board << 3n;
227 buffer[bufferIndex++] = insertionBoard;
228
229 // Generate board with insertion point at each position
230 while (true) {
231 const currentBall = zuma.board & ballMask;
232
233 // End of board reached
234 if (currentBall === 0n) {
235 break;
236 }
237
238 ballMask <<= 3n;
239 // Move ball and create space for next insertion
240 insertionBoard = (insertionBoard | currentBall) & ~ballMask;
241 buffer[bufferIndex++] = insertionBoard;
242 }
243 return bufferIndex;
244}
245
246/**
247 * Encode string state into bit-packed bigint
248 * @param stateStr String representation of state
249 * @param sortFlag Whether to sort characters before encoding
250 * @return Encoded state as bigint (3 bits per ball)
251 */
252function encode(stateStr: string, sortFlag: boolean): bigint {
253 const stateChars = stateStr.split('');
254
255 // Sort for consistent hand representation
256 if (sortFlag) {
257 stateChars.sort();
258 }
259
260 let encodedBits = 0n;
261 // Pack each character as 3 bits
262 for (const ch of stateChars) {
263 encodedBits = (encodedBits << 3n) | encodeChar(ch);
264 }
265 return encodedBits;
266}
267
268/**
269 * Encode single character to 3-bit representation
270 * @param ch Character representing ball color
271 * @return 3-bit encoded value
272 */
273function encodeChar(ch: string): bigint {
274 switch (ch) {
275 case 'R': return 0x1n; // Red
276 case 'G': return 0x2n; // Green
277 case 'B': return 0x3n; // Blue
278 case 'W': return 0x4n; // White
279 case 'Y': return 0x5n; // Yellow
280 case ' ': return 0x0n; // Empty/delimiter
281 default: throw new Error(`Invalid char: ${ch}`);
282 }
283}
284Time and Space Complexity
Time Complexity: O(n * m! * n^2 * k)
Where:
nis the length of the board stringmis the length of the hand string (number of balls in hand)kis the average number of iterations needed for theremovefunction to stabilize
The analysis breaks down as follows:
- The BFS explores different states where we try placing balls from the hand into different positions on the board
- In the worst case, we can have up to
m!different orderings of using the balls from the hand - For each state, we iterate through unique balls in the hand (at most
mballs) - For each ball, we try inserting it at
n+1possible positions in the board - After each insertion, the
removefunction is called which takesO(n*k)time, wherekiterations are needed for the regex substitution to stabilize (typically small constant) - The regex substitution itself takes
O(n)per iteration - Overall:
O(m! * m * n * n * k) = O(n * m! * n^2 * k)
Space Complexity: O(n * m! * n)
The space complexity is determined by:
- The
visitedset which can store up toO(m! * n)different board states (different combinations of balls placed at different positions) - The BFS queue which in the worst case can hold
O(m! * n)states - Each state string takes
O(n)space - The recursive call stack is not present here as the solution uses iterative BFS
- Total space:
O(n * m! * n)
Common Pitfalls
1. Inefficient Duplicate Ball Handling
One major pitfall is how the code handles duplicate balls in the hand. While using set(remaining_balls) prevents trying the same color multiple times in one BFS level, the current implementation has a subtle inefficiency:
The Problem: When you have multiple balls of the same color (e.g., "RRB"), the algorithm will eventually explore inserting each 'R' at every position, creating many duplicate states through different paths.
Example:
- Hand: "RRB", Board: "WW"
- Path 1: Use first R → State ("RWW", "RB")
- Path 2: Use second R → State ("RWW", "RB")
- Both paths lead to the same state but through different "R" balls
Solution:
Track states as (board, sorted_hand) pairs instead of just board states:
visited_states = set()
queue = deque([(board, hand)])
while queue:
current_board, remaining_balls = queue.popleft()
# Create a canonical representation of the state
state_key = (current_board, ''.join(sorted(remaining_balls)))
if state_key in visited_states:
continue
visited_states.add(state_key)
if not current_board:
return len(hand) - len(remaining_balls)
# rest of the code...
2. Unnecessary Insertion Positions
The current code tries inserting at every position from 0 to len(current_board), but many of these insertions are redundant:
The Problem: Inserting a ball between identical consecutive balls doesn't create different outcomes. For example, with board "WWWW", inserting 'R' at positions 1, 2, or 3 all result in effectively the same state after processing.
Solution: Skip positions where the ball would be inserted between identical characters:
for insert_position in range(len(current_board) + 1):
# Skip if inserting between two identical balls (except if it's the ball we're inserting)
if (insert_position > 0 and
insert_position < len(current_board) and
current_board[insert_position - 1] == current_board[insert_position] and
current_board[insert_position] != ball_color):
continue
new_board = current_board[:insert_position] + ball_color + current_board[insert_position:]
# rest of the code...
3. Memory Explosion with Large Inputs
The visited set can grow exponentially with board and hand size, potentially causing memory issues.
The Problem: Each unique board configuration is stored, and with many possible intermediate states, memory usage can balloon quickly.
Solution: Implement state pruning by limiting exploration depth or using iterative deepening:
def findMinStep(self, board: str, hand: str) -> int:
# Try with increasing depth limits
for max_depth in range(1, len(hand) + 1):
result = self.bfs_with_depth_limit(board, hand, max_depth)
if result != -1:
return result
return -1
def bfs_with_depth_limit(self, board, hand, max_depth):
visited_states = set()
queue = deque([(board, hand, 0)]) # Added depth counter
while queue:
current_board, remaining_balls, depth = queue.popleft()
if depth > max_depth:
continue
if not current_board:
return depth
# Continue with normal BFS logic...
4. Regex Performance Issues
The regex pattern matching can be slow for very long strings or when called repeatedly.
The Problem:
Regex compilation happens on every call to remove_consecutive_balls, and pattern matching can be expensive.
Solution: Pre-compile the regex pattern and consider a non-regex approach for better performance:
# Pre-compile regex (class-level or module-level)
REMOVAL_PATTERN = re.compile(r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}')
def remove_consecutive_balls(board_state):
while board_state:
new_board = REMOVAL_PATTERN.sub('', board_state)
if len(new_board) == len(board_state):
break
board_state = new_board
return board_state
# Alternative non-regex approach
def remove_consecutive_balls_fast(board_state):
while True:
result = []
i = 0
changed = False
while i < len(board_state):
j = i
while j < len(board_state) and board_state[j] == board_state[i]:
j += 1
if j - i < 3:
result.extend(board_state[i:j])
else:
changed = True
i = j
board_state = ''.join(result)
if not changed:
break
return board_state
These optimizations can significantly improve both time and space complexity, especially for larger inputs where the state space explosion becomes problematic.
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:
How does merge sort divide the problem into subproblems?
Recommended Readings
Stack Intro
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
BFS Fundamentals
https assets algo monster 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 Breadth First Search BFS
Memoization
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
Want a Structured Path to Master System Design Too? Don’t Miss This!