Facebook Pixel

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:

  1. 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)

  2. 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.

  3. Win Condition: You win when the board becomes empty (all balls cleared)

  4. 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:

  1. We're exploring a state space where each state is a (board, hand) configuration
  2. We need the minimum number of moves (shortest path in an unweighted graph)
  3. BFS guarantees finding the optimal solution by exploring states level by level
  4. 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:

  1. 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.

  2. 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.

  3. 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 position i
    • 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 visited reduces 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 Evaluator

Example 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!

Result: Minimum insertions = 2

Why BFS finds this optimal solution:

  1. 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
  2. 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
  3. 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
56
1class 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}
280
1#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};
331
1/**
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}
284

Time and Space Complexity

Time Complexity: O(n * m! * n^2 * k)

Where:

  • n is the length of the board string
  • m is the length of the hand string (number of balls in hand)
  • k is the average number of iterations needed for the remove function 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 m balls)
  • For each ball, we try inserting it at n+1 possible positions in the board
  • After each insertion, the remove function is called which takes O(n*k) time, where k iterations 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 visited set which can store up to O(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:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More