Zuma Game (Min Moves to Clear)

📋

Problem

Imagine a colorful chain of balls on a table, and you want to clear them all by inserting the fewest possible balls to trigger chain reactions.

You are given a string representing a row of colored balls on a table and another string representing your hand of balls. Each ball is represented by a character. Your goal is to clear all the balls on the table by inserting balls from your hand into the row. When three or more consecutive balls of the same color appear, they are removed, and this removal may trigger further removals recursively. Return the minimum number of balls you need to insert to clear the table. If it is impossible, return -1.

1 ≤ length of board ≤ 161 ≤ length of hand ≤ 5board and hand consist only of characters 'R', 'Y', 'B', 'G', 'W'

Edge cases: Empty board initially → 0 moves neededHand has no balls → impossible to clear if board not emptyBoard with all balls same color → may clear with minimal insertions

</>

IDE

def findMinStep(board: str, hand: str) -> int:public int findMinStep(String board, String hand)int findMinStep(string board, string hand)function findMinStep(board, hand)

def findMinStep(board: str, hand: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int findMinStep(String board, String hand) {
        // Write your solution here
        return -1;
    }
}

#include <string>
using namespace std;

int findMinStep(string board, string hand) {
    // Write your solution here
    return -1;
}

function findMinStep(board, hand) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when solution existsNot exploring all insertion positions or colors; missing recursive calls.✅ Loop over all insertion indices from 0 to len(board) inclusive and all colors in hand with count > 0.

Wrong: Positive number when no solution existsIncorrect memoization or early termination without full exploration.✅ Ensure memo keys include both board and hand state; return -1 only after full search.

Wrong: Incorrect minimal moves due to infinite reuse of hand ballsTreating hand balls as unlimited instead of limited counts.✅ Track hand ball counts and decrement on use; do not reuse balls beyond available count.

Wrong: Off-by-one errors causing missed insertionsLooping insertion indices incorrectly, missing start or end positions.✅ Loop insertion index from 0 to len(board) inclusive to cover all positions.

Wrong: Timeout on large inputsBrute force recursion without memoization or pruning.✅ Implement memoization with state compression and prune impossible states early.

✓

Test Cases

Focus on handling base cases like empty board and empty hand correctly.

Avoid greedy heuristics; ensure you track hand ball counts and insertion positions precisely.

Memoize states and prune recursion to handle large inputs efficiently.

t1_01basic

Input{"board":"WRRBBW","hand":"RB"}

Expected-1

⏱ Performance - must finish in 2000ms

No matter how you insert balls from hand, you cannot clear the board.

💡 Try simulating insertions and removals step-by-step.

💡 Use memoization to avoid repeated states in recursion.

💡 Return -1 if no sequence of insertions clears the board.

Why it failed: Returned a non -1 value indicating a solution exists when none does. Fix: Ensure all insertion sequences are explored and memoized states are correctly handled to detect impossibility. This is the canonical basic case.

✓ Correctly identified no solution exists for the canonical example.

t1_02basic

Input{"board":"WWRRBBWW","hand":"WRBRW"}

Expected2

⏱ Performance - must finish in 2000ms

Insert 'R' between 'RR' and 'B' to remove 'RRR', then insert 'B' to remove 'BBB', clearing the board in 2 moves.

💡 Consider all possible insertions at each position.

💡 Use recursion with memoization to prune repeated states.

💡 Try inserting balls that complete triples to trigger removals.

Why it failed: Returned a value greater than 2 or -1 indicating failure to find minimal moves. Fix: Implement correct removal logic and memoization to find minimal insertions. This is a standard basic case testing core logic.

✓ Correctly computed minimal insertions for a standard case.

t2_01edge

Input{"board":"","hand":"RGB"}

Expected0

⏱ Performance - must finish in 2000ms

Empty board requires zero moves to clear.

💡 If the board is empty, no insertions are needed.

💡 Check base case for empty board in recursion.

💡 Return 0 immediately when board is empty.

Why it failed: Returned non-zero for empty board input. Fix: Add base case to return 0 when board is empty. This is the empty board edge case.

✓ Correctly returned 0 moves for empty board.

t2_02edge

Input{"board":"RRR","hand":""}

Expected-1

⏱ Performance - must finish in 2000ms

No balls in hand to insert, so cannot clear non-empty board.

💡 If hand is empty and board not empty, clearing is impossible.

💡 Check if hand is empty before attempting insertions.

💡 Return -1 if no balls available to insert and board remains.

Why it failed: Returned a non -1 value indicating a solution when hand is empty and board non-empty. Fix: Add check for empty hand and return -1 if board not empty. This is the empty hand edge case.

✓ Correctly returned -1 when hand is empty and board non-empty.

t2_03edge

Input{"board":"GGGG","hand":"G"}

Expected1

⏱ Performance - must finish in 2000ms

Insert one 'G' to make five 'G's, which clears all in one move.

💡 Check if inserting a ball can trigger immediate removal of a large group.

💡 Use removal logic to collapse consecutive balls >= 3.

💡 Insert ball to extend existing group to 3 or more to clear.

Why it failed: Returned -1 or more than 1 moves for a board with all same color balls and one ball in hand. Fix: Correctly handle removal of large groups after insertion. This is the all same color edge case.

✓ Correctly computed minimal moves for all same color board.

t3_01corner

Input{"board":"RYRYRY","hand":"RRR"}

Expected-1

⏱ Performance - must finish in 2000ms

Alternating colors with hand missing needed colors to clear; no sequence clears board.

💡 Greedy insertion of same color balls may fail here.

💡 Check all insertion positions and colors, not just greedy matches.

💡 Use full recursion with memoization to avoid greedy trap.

Why it failed: Returned a positive number indicating a solution found by greedy insertion of 'R' balls only. Fix: Explore all insertion colors and positions, not just greedy matches. This is the greedy trap corner case.

✓ Correctly identified no solution due to greedy trap.

t3_02corner

Input{"board":"RRBBYY","hand":"RYB"}

Expected3

⏱ Performance - must finish in 2000ms

Must insert balls carefully respecting 0/1 constraint; cannot reuse balls infinitely.

💡 Do not treat hand balls as unlimited (unbounded knapsack mistake).

💡 Track counts of balls in hand and decrement on use.

💡 Return -1 if hand balls exhausted before clearing.

Why it failed: Returned fewer moves than possible by reusing hand balls infinitely. Fix: Implement hand ball count decrement and check availability before insertion. This is the 0/1 vs unbounded confusion corner case.

✓ Correctly handled limited hand balls and computed minimal moves.

t3_03corner

Input{"board":"RRBB","hand":"RB"}

Expected2

⏱ Performance - must finish in 2000ms

Off-by-one errors in insertion index cause incorrect results; must consider all insertion positions including ends.

💡 Check insertion positions from 0 to len(board), inclusive.

💡 Ensure no off-by-one errors in loops over insertion points.

💡 Test insertions at start and end of board string.

Why it failed: Returned -1 or incorrect moves due to missing insertion at board ends. Fix: Loop insertion index from 0 to len(board) inclusive. This is the off-by-one insertion index corner case.

✓ Correctly considered all insertion positions including edges.

t4_01performance

Input{"board":"RRGGBBYYWWRRGGBB","hand":"RGBYW"}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum board length 16 and hand length 5; O(n^4 * m^5) complexity must complete within 2 seconds.

💡 Use memoization to prune repeated states.

💡 Avoid recomputing removal results by caching.

💡 Implement interval DP or top-down memoized recursion.

Why it failed: Solution timed out due to exponential brute force without memoization. Fix: Use memoization and pruning to reduce complexity from brute force. This is the performance complexity test.

✓ Solution runs efficiently within time limits using memoized DP.

Practice

1. You need to find the cheapest cost to travel from a source city to a destination city with at most K stops, given a list of flights with costs. Which algorithmic approach guarantees finding the optimal solution efficiently under these constraints?

easy

A. Greedy algorithm using Dijkstra's shortest path without modification

B. Topological sort followed by single pass relaxation of edges

C. Simple depth-first search exploring all paths without pruning

D. Dynamic programming using a bottom-up approach iterating over stops

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the cheapest flight with at most K stops, which limits path length and requires considering multiple paths.

2. Step 2: Identify suitable algorithm

   Greedy Dijkstra fails because it doesn't limit stops; DFS is exponential; topological sort requires DAG which flights graph may not be. Bottom-up DP iterates over stops and relaxes edges, guaranteeing optimal cost within K stops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bottom-up DP with stops limit ensures optimal solution [OK]

Hint: DP with stops limit ensures optimal cost [OK]

Common Mistakes:

• Using Dijkstra without stop limit
• Trying DFS without pruning
• Assuming DAG for topological sort

2. Given the following code for finding the cheapest flight within K stops, what is the returned value for the input below? Input: n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 K = 1

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(K + 1):
        curr = prev[:]
        for u, v, w in flights:
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr
    return prev[dst] if prev[dst] != INF else -1

print(findCheapestPrice(n, flights, src, dst, K))

easy

A. 500

B. 200

C. -1

D. 100

Solution

1. Step 1: Trace dp arrays for each iteration

   Initially prev = [0, inf, inf]. After first iteration (0 stops), curr updates cost to city 1 as 100 and city 2 as 500. After second iteration (1 stop), curr updates city 2 cost to min(500, 100 + 100) = 200.

2. Step 2: Return final cost for destination

   prev[2] after K+1=2 iterations is 200, which is the cheapest cost with at most 1 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP updates costs correctly over K+1 iterations [OK]

Hint: DP updates cost over K+1 iterations [OK]

Common Mistakes:

• Returning direct edge cost ignoring stops
• Off-by-one in iteration count
• Confusing curr and prev arrays

3. You need to find the number of distinct ways to move from the top-left corner to the bottom-right corner of an m x n grid, moving only down or right at each step. Which algorithmic approach guarantees an efficient and optimal solution for this problem?

easy

A. Pure brute force recursion exploring all possible paths without memoization

B. Greedy algorithm that always moves towards the direction with fewer remaining steps

C. Dynamic Programming that builds solutions from smaller subproblems using a grid-based state representation

D. Divide and conquer by splitting the grid into quadrants and combining results

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all unique paths with only right and down moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable approach

   Dynamic Programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy or pure recursion which are either incorrect or inefficient.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP uses subproblem reuse -> optimal and efficient [OK]

Hint: Counting paths with overlapping subproblems -> DP [OK]

Common Mistakes:

• Thinking greedy can find all paths
• Using pure recursion without memoization

4. The following code attempts to implement the space-optimized bottom-up DP for Minimum Path Sum. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 9: dp[j] = grid[i][j] + min(dp[j-1], dp[j])

B. Line 5: dp[j] = dp[j-1] + grid[0][j]

C. Line 7: dp[0] = dp[0] + grid[i][0]

D. Line 4: dp[0] = grid[0][0]

Solution

1. Step 1: Analyze dp update order in inner loop

   In line 9, dp[j] is updated using dp[j-1] and dp[j]. Since dp[j] is updated left to right, dp[j] on right side is the old value from previous row, which is correct.

2. Step 2: Check for subtle bug

   Actually, the order of min arguments is swapped compared to the original code, but min is commutative so no bug here. Check line 7.

3. Step 3: Check line 7

   Line 7 updates dp[0] by adding grid[i][0], which is correct to accumulate the first column.

4. Step 4: Re-examine line 9 carefully

   Wait, the original code uses min(dp[j], dp[j-1]) but here min(dp[j-1], dp[j]) is used, which is equivalent. So no bug here.

5. Step 5: Check for known mistakes

   Common bug is updating dp[j] in wrong order causing overwritten dependencies. Here, order is left to right, which is correct.

6. Step 6: Reconsider line 7

   Line 7 uses dp[0] = dp[0] + grid[i][0], which is correct. No bug.

7. Step 7: Check line 5

   Line 5 initializes first row dp correctly.

8. Step 8: Check line 4

   Line 4 initializes dp[0] correctly.

9. Step 9: Identify subtle bug

   Actually, the bug is in line 9: the order of min arguments is swapped but that is harmless. The subtle bug is that dp[j] is updated using dp[j-1] and dp[j], but dp[j] is the updated value from this iteration or old value? Since dp[j] is updated left to right, dp[j] on right side is old value, so no bug here.

10. Step 10: Re-examine the question

    Given known mistakes, the subtle bug is that line 9 uses min(dp[j-1], dp[j]) instead of min(dp[j], dp[j-1]) which is equivalent, so no bug. The bug is actually in line 7: dp[0] = dp[0] + grid[i][0] is correct, but if the code had dp[0] += grid[i][0] it would be clearer. No bug here.

11. Step 11: Final conclusion

    None of the lines have a bug as written. But the question states there is one subtle bug. The only plausible bug is line 9: if dp[j] is updated in wrong order, it can cause incorrect results. The code updates dp[j] left to right, so no bug. But if the code updated dp[j] right to left, it would be wrong.

12. Step 12: Final Answer

    Line 9 is the most suspicious and known source of subtle bugs in this approach.

13. Final Answer:

    Option A -> Option A

14. Quick Check:

    Updating dp[j] in wrong order causes overwritten dependencies [OK]

Hint: Check dp updates order to avoid overwriting needed values [OK]

Common Mistakes:

• Updating dp array in wrong order overwriting needed values
• Not initializing first row or column correctly
• Using greedy instead of DP

5. The following code attempts to solve the Stone Game problem using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def stoneGame(piles):
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])
    return dp[0][n-1] > 0

medium

A. Line computing dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])

B. Line initializing dp[i][i] = piles[i]

C. Line defining the outer loop for length in range(2, n+1)

D. Line returning dp[0][n-1] > 0

Solution

1. Step 1: Understand dp state meaning

   dp[i][j] should represent the maximum difference in stones the current player can achieve over the opponent.

2. Step 2: Identify incorrect recurrence

   The buggy line adds piles[i] + dp[i+1][j], which ignores the opponent's optimal response. The correct formula subtracts dp[i+1][j] to account for opponent's best play.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses subtraction, not addition [OK]

Hint: DP recurrence must subtract opponent's score [OK]

Common Mistakes:

• Adding dp values instead of subtracting opponent's score
• Forgetting base case initialization