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. Consider the following Python code implementing the Cherry Pickup problem using bottom-up DP. Given the input grid below, what is the final returned value?

grid = [
  [0, 1, -1],
  [1, 0, -1],
  [1, 1,  1]
]

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]
    dp[0][0][0] = grid[0][0]
    for step in range(1, 2 * (n - 1) + 1):
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):
            c1 = step - r1
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):
                c2 = step - r2
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                candidates = []
                if r1 > 0 and r2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2 - 1])
                if r1 > 0 and c2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2])
                if c1 > 0 and r2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2 - 1])
                if c1 > 0 and c2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2])
                best_prev = max(candidates) if candidates else -float('inf')
                if best_prev == -float('inf'):
                    continue
                val = best_prev + grid[r1][c1]
                if r1 != r2:
                    val += grid[r2][c2]
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)
    return max(0, dp[n - 1][n - 1][n - 1])

print(cherryPickup(grid))

easy

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace dp states for step=4 (final step for 3x3 grid)

   At step=4, both players reach bottom-right (2,2). The dp value dp[2][2][2] accumulates max cherries collected along valid paths avoiding thorns (-1).

2. Step 2: Calculate max cherries collected

   By tracing paths, max cherries collected is 6, considering both players' paths and avoiding double counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual path tracing confirms max cherries = 6 [OK]

Hint: Trace dp at final step for both players [OK]

Common Mistakes:

• Off-by-one errors in step or indices
• Double counting cherries when players overlap
• Ignoring thorn cells leading to invalid paths

2. You are given an n x n integer matrix. You want to find a path from the top row to the bottom row such that you move one step down each time, and at each step you can move to the same column, the column to the left, or the column to the right. The goal is to minimize the sum of the values along this path. Which algorithmic approach guarantees finding the minimum sum efficiently?

easy

A. Greedy algorithm that picks the minimum adjacent value at each step

B. Sorting each row and picking the smallest values independently

C. Depth-first search exploring all paths without memoization

D. Dynamic programming that builds solutions row by row using previous row results

Solution

1. Step 1: Understand the problem constraints

   The problem requires considering all possible paths moving down and diagonally, which suggests overlapping subproblems and optimal substructure.

2. Step 2: Identify the suitable algorithm

   Dynamic programming fits because it efficiently computes minimum sums for each cell based on the previous row's results, avoiding redundant calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy and sorting fail to consider future steps; DFS without memoization is exponential [OK]

Hint: DP uses previous row results to build solutions [OK]

Common Mistakes:

• Thinking greedy or sorting per row suffices
• Ignoring overlapping subproblems

3. What is the time complexity of the bottom-up dynamic programming solution for the Dungeon Game problem on an m x n grid, and why might some candidates mistakenly think it is higher?

medium

A. O(2^{m+n}) because all paths are explored recursively

B. O(m + n) since only one path is considered at a time

C. O(m * n * max(|dungeon[i][j]|)) due to health value range affecting computations

D. O(m * n) because each cell is computed once using constant time operations

Solution

1. Step 1: Identify loops

   The bottom-up DP uses nested loops over m rows and n columns, each cell computed once.

2. Step 2: Analyze per-cell work

   Each dp[i][j] calculation is O(1), involving min and max operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP table size m*n and constant work per cell [OK]

Hint: DP fills m*n table once, no recursion overhead [OK]

Common Mistakes:

• Confusing brute force recursion with DP
• Thinking health values affect complexity

4. Consider the following buggy code for Paint House (K Colors). Which line contains the subtle bug that can cause adjacent houses to have the same color, violating constraints?

medium

A. Line with 'min_prev = min(dp[x] for x in range(k))'

B. Line with 'dp = costs[0][:]' initialization

C. Line with 'new_dp = [0]*k' inside the loop

D. Line with 'return min(dp)' at the end

Solution

1. Step 1: Identify constraint violation

   The problem requires that adjacent houses cannot have the same color. The code must exclude the current color when computing min_prev.

2. Step 2: Locate bug in min_prev calculation

   The line 'min_prev = min(dp[x] for x in range(k))' includes the current color's dp value, allowing same color adjacency, violating constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Excluding current color in min calculation is essential [OK]

Hint: Check if min excludes current color to avoid same-color adjacency [OK]

Common Mistakes:

• Including current color in min calculation
• Incorrect dp initialization
• Returning min(dp) without proper updates

5. Suppose the Cherry Pickup problem is modified so that players can revisit cells multiple times (i.e., cycles allowed), and cherries are replenished after being picked (can be collected multiple times). Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Use the same 3D DP with memoization but remove the check that prevents revisiting cells.

B. Apply a greedy approach that always moves players to the next cell with the highest cherry count.

C. Use a 4D DP tracking both players' full positions and number of visits per cell to avoid double counting.

D. Switch to a shortest path algorithm like Dijkstra on a state graph representing both players' positions and steps, allowing cycles.

Solution

1. Step 1: Understand the impact of allowing revisits and replenished cherries

   Cycles and replenished cherries mean the problem is no longer acyclic and DP assumptions break down.

2. Step 2: Identify suitable algorithm

   Modeling the problem as a shortest path on a state graph with both players' positions and steps allows handling cycles and repeated cherry collection correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP fails with cycles; shortest path algorithms handle repeated states [OK]

Hint: Cycles break DP; use graph shortest path [OK]

Common Mistakes:

• Removing DP constraints without changing algorithm
• Adding dimensions to DP without handling cycles
• Using greedy which ignores global optimality