Zuma Game (Min Moves to Clear)

▶

Steps

setup

Initialize hand count and memo dictionary

Count the balls in hand and prepare memoization storage to cache results for subproblems.

💡 Counting hand balls upfront allows quick checks on availability during recursion.

Line:

hand_count = Counter(hand)
memo = {}

💡 Hand ball counts are essential for deciding if insertion is possible at each step.

setup

Start DP on full board "WRRBBW" with hand counts {'R':1,'B':1}

Begin recursive dp call on the entire board substring with the initial hand ball counts.

💡 This is the root problem: clear the whole board with all hand balls available.

Line:

return dp(board, hand_count)

💡 The algorithm will try all possible insertions and splits starting from the full board.

fill_cells

Check first group 'W' at indices [0..0], balls needed = 2

Identify the first consecutive group 'W' of length 1 and calculate balls needed to remove it (3 - 1 = 2).

💡 Groups shorter than 3 need balls inserted to be removed.

Line:

while i < len(s):
  j = i
  while j < len(s) and s[j] == s[i]:
    j += 1
  balls_needed = 3 - (j - i)

💡 We must insert 2 'W' balls from hand to remove this group if possible.

compare

Check if hand has enough 'W' balls to remove group

Verify if hand_count['W'] >= 2 to remove the 'W' group by insertion.

💡 If not enough balls, this group cannot be removed now.

Line:

if hand_count[c] >= balls_needed:

💡 No insertion possible here; must try next group.

fill_cells

Check second group 'RR' at indices [1..2], balls needed = 1

Identify the next group 'RR' of length 2 and calculate balls needed to remove it (3 - 2 = 1).

💡 Groups closer to 3 need fewer insertions.

Line:

while i < len(s):
  j = i
  while j < len(s) and s[j] == s[i]:
    j += 1
  balls_needed = 3 - (j - i)

💡 We need 1 'R' ball to remove this group.

compare

Check if hand has enough 'R' balls to remove 'RR' group

Verify if hand_count['R'] >= 1 to remove 'RR' group by insertion.

💡 If yes, try removing and recurse on the new board.

Line:

if hand_count[c] >= balls_needed:

💡 We can insert 1 'R' ball to remove 'RR' group.

expand

Remove 'RR' group and apply remove_consecutive

Remove 'RR' group from board, resulting in "WBBBW", then remove consecutive groups of 3 or more.

💡 Removing groups may cause chain reactions clearing more balls.

Line:

new_s = s[:i] + s[j:]
new_s = remove_consecutive(new_s)

💡 After removal, the board is "WBBBW" with no further consecutive removals.

fill_cells

Recurse dp on "WBBBW" with hand_count {'R':0,'B':1}

Call dp recursively on the new board substring with one less 'R' ball in hand.

💡 Recursion explores if the smaller board can be cleared with remaining balls.

Line:

temp = dp(new_s, hand_count)

💡 This subproblem is smaller and will be solved similarly.

fill_cells

Check group 'W' at start of "WBBBW", balls needed = 2

Identify 'W' group length 1 needing 2 balls to remove, but hand has no 'W' balls.

💡 Cannot remove this group now, must try next group.

Line:

balls_needed = 3 - (j - i)
if hand_count[c] >= balls_needed:

💡 No insertion possible for 'W' group here.

fill_cells

Check group 'BBB' at indices [1..3], balls needed = 0

Group 'BBB' length 3 can be removed without insertion.

💡 Groups of 3 or more are removed automatically.

Line:

balls_needed = 3 - (j - i)

💡 Removing 'BBB' reduces board to "WW".

fill_cells

Recurse dp on "WW" with hand_count {'R':0,'B':1}

Try clearing "WW" with current hand balls.

💡 Smaller substring, fewer balls to clear.

Line:

temp = dp(new_s, hand_count)

💡 Try to insert balls to remove 'WW'.

fill_cells

Check group 'WW' needing 1 ball to remove

Group 'WW' length 2 needs 1 'W' ball, but hand has 0 'W' balls.

💡 Cannot remove this group, no 'W' balls in hand.

Line:

if hand_count[c] >= balls_needed:

💡 No way to clear this substring.

prune

Return -1 for "WW" subproblem, propagate up

No solution found for "WW", so this path is invalid.

💡 DP memoizes -1 to avoid re-exploring this state.

Line:

memo[key] = -1 if res == float('inf') else res
return memo[key]

💡 This subproblem cannot be cleared with current hand.

prune

Back to "WBBBW", no better solution found, return -1

Since recursive call returned -1, no solution removing 'RR' group here.

💡 Try next groups or conclude no solution.

Line:

if temp != -1:
  res = min(res, balls_needed + temp)

💡 No way to clear board by removing 'RR' group first.

fill_cells

Check third group 'BB' at indices [3..4], balls needed = 1

Next group 'BB' length 2 needs 1 'B' ball to remove.

💡 Try removing this group if hand has 'B' balls.

Line:

balls_needed = 3 - (j - i)

💡 Hand has 1 'B' ball, so removal is possible.

expand

Remove 'BB' group and apply remove_consecutive

Remove 'BB' group from board, resulting in "WRRW", then remove consecutive groups.

💡 Removing groups may cause chain reactions clearing more balls.

Line:

new_s = s[:i] + s[j:]
new_s = remove_consecutive(new_s)

💡 After removal, board is "WRRW" with no further removals.

fill_cells

Recurse dp on "WRRW" with hand_count {'R':1,'B':0}

Try clearing "WRRW" with updated hand balls.

💡 Explore if this smaller board can be cleared.

Line:

temp = dp(new_s, hand_count)

💡 Try removing groups or inserting balls as needed.

fill_cells

Check group 'RR' at indices [1..2], balls needed = 1

Group 'RR' length 2 needs 1 'R' ball to remove, hand has 1 'R' ball.

💡 Try removing this group by inserting 1 'R' ball.

Line:

balls_needed = 3 - (j - i)
if hand_count[c] >= balls_needed:

💡 Removing 'RR' may simplify board further.

expand

Remove 'RR' group, board becomes "WW"

After removal, board is "WW" with no further removals.

💡 Try clearing "WW" with no 'R' balls left in hand.

Line:

new_s = s[:i] + s[j:]
new_s = remove_consecutive(new_s)

💡 No 'R' balls left, must check if 'WW' can be cleared.

prune

No balls left to remove 'WW', return -1 and conclude no solution

No balls in hand to remove 'WW', so return -1 for this path and propagate up.

💡 All attempts fail, so the board cannot be cleared.

Line:

memo[key] = -1 if res == float('inf') else res
return memo[key]

💡 The final answer is -1, meaning no solution exists.

from collections import Counter
import sys
sys.setrecursionlimit(10**7)

def findMinStep(board: str, hand: str) -> int:
    hand_count = Counter(hand)  # STEP 1
    memo = {}  # STEP 1

    def remove_consecutive(s):  # STEP 7, 16, 19
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                s = s[:i] + s[j:]
                i = 0
            else:
                i += 1
        return s

    def dp(s, hand_count):
        if not s:
            return 0
        key = (s, tuple(sorted(hand_count.items())))
        if key in memo:
            return memo[key]
        res = float('inf')
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            balls_needed = 3 - (j - i)  # STEP 3,5,9,10,15,18,20
            c = s[i]
            if hand_count[c] >= balls_needed:  # STEP 4,6,12,18,20
                hand_count[c] -= balls_needed  # STEP 6,16,18
                new_s = s[:i] + s[j:]
                new_s = remove_consecutive(new_s)  # STEP 7,16,19
                temp = dp(new_s, hand_count)  # STEP 8,11,17
                if temp != -1:
                    res = min(res, balls_needed + temp)  # STEP 14
                hand_count[c] += balls_needed
            i = j
        memo[key] = -1 if res == float('inf') else res  # STEP 13,20
        return memo[key]

    return dp(board, hand_count)  # STEP 2

if __name__ == '__main__':
    print(findMinStep("WRRBBW", "RB"))  # Output: -1
    print(findMinStep("WWRRBBWW", "WRBRW"))  # Output: 2

📊

Zuma Game (Min Moves to Clear) - Watch the Algorithm Execute, Step by Step

Watching each insertion attempt and recursive call reveals how interval DP breaks down the problem and why some states are impossible to clear.

Item 0 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	?	?	?	?	?	?

Item 0 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	R	R	B	B	W

full board

Item 0 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	R	R	B	B	W

'W' group

Item 0 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	R	R	B	B	W

not enough 'W' balls

Item 1 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	R	R	B	B	W

'RR' group

Item 1 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	R	R	B	B	W

insert 'R' ball

Item 1 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	B	B	B	W	?

board after removal

Item 1 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	B	B	B	W	?

recursive call

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0	W	B	B	B	W

not enough 'W' balls

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0	W	W	?	?	?

remove 'BBB'

Item 0 - wt:0 val:0

i\w	0	1
i=0	W	W

recursive call

Item 0 - wt:0 val:0

i\w	0	1
i=0	W	W

not enough 'W' balls

Item 0 - wt:0 val:0

i\w	0	1
i=0	-1	?

no solution

Item 1 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	B	B	B	W	-1

no solution

Item 3 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	R	R	B	B	W

'BB' group

Item 3 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	W	R	R	W	?	?

board after removal

Item 0 - wt:0 val:0

i\w	0	1	2	3
i=0	W	R	R	W

recursive call

Item 1 - wt:0 val:0

i\w	0	1	2	3
i=0	W	R	R	W

insert 'R' ball

Item 1 - wt:0 val:0

i\w	0	1
i=0	W	W

board after removal

Item 0 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	-1	?	?	?	?	?

final no solution

Key Takeaways

✓ Interval DP breaks the problem into smaller substrings and uses memoization to avoid recomputation.

This is hard to see from code alone because recursion and memoization interplay is subtle.

✓ The algorithm tries all groups and possible insertions, pruning impossible paths early.

Visualizing each insertion attempt clarifies why some states fail and others succeed.

✓ Chain reactions from removing groups simplify the board and reduce problem size.

Watching remove_consecutive in action reveals how the board changes dynamically.

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. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n, and why?

medium

A. O(n^3) because for each interval we try all possible last balloons to burst

B. O(n^3) due to three nested loops iterating over intervals and burst positions

C. O(2^n) because of the exponential number of burst orders

D. O(n^2) because we fill a 2D dp table of size n by n

Solution

1. Step 1: Identify loops in bottom-up DP

   There are three nested loops: length of interval (up to n), start index i (up to n), and position k (up to n) inside the interval.

2. Step 2: Calculate complexity

   Each loop runs up to n times, so total time is O(n * n * n) = O(n^3). The dp table is size O(n^2), but filling it requires the third loop over k.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over n -> O(n^3) time complexity [OK]

Hint: Three nested loops over intervals and positions cause cubic time [OK]

Common Mistakes:

• Confusing dp table size with time complexity
• Ignoring the innermost loop over k
• Assuming exponential time for DP solution

3. The following code attempts to compute the minimum falling path sum using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            dp[j] = matrix[i][j] + best

    return min(dp)

medium

A. Line 7: Updating dp[j] inside the inner loop without backup

B. Line 9: Checking if j > 0 before accessing dp[j-1]

C. Line 3: dp initialization with matrix[0][:]

D. Line 12: Returning min(dp) after the loops

Solution

1. Step 1: Understand dp update logic

   dp array holds minimum sums for previous row. Updating dp[j] in place overwrites values needed for neighbors in the same iteration.

2. Step 2: Identify the bug

   Updating dp[j] inside the inner loop without using a separate array causes premature overwriting, leading to incorrect neighbor comparisons.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using a separate new_dp array fixes the bug [OK]

Hint: Don't overwrite dp while still reading from it in same iteration [OK]

Common Mistakes:

• Updating dp in place without backup
• Ignoring boundary checks

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

5. Suppose the problem is modified so that you can reuse the same color for adjacent houses, but you want to minimize the total cost. Which modification to the DP solution is correct?

hard

A. Use brute force recursion without memoization since constraints are relaxed.

B. Keep excluding the previous color but add a penalty cost for same color adjacency.

C. Remove the condition excluding the previous color when computing min_prev; just take min(dp) for all colors.

D. Use a greedy approach picking the cheapest color for each house independently.

Solution

1. Step 1: Understand constraint relaxation

   Allowing same color for adjacent houses removes the need to exclude previous color in DP transitions.

2. Step 2: Modify DP accordingly

   Now min_prev is simply min(dp) over all colors, no exclusion needed. This simplifies the DP and still finds minimum cost.

3. Step 3: Evaluate other options

   Adding penalty is unnecessary. Brute force is inefficient. Greedy fails because costs vary per house and color.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Relaxed constraints allow including all colors in min calculation [OK]

Hint: Relaxed constraints mean no exclusion of previous color in DP [OK]

Common Mistakes:

• Still excluding previous color unnecessarily
• Adding penalty complicates solution
• Using brute force or greedy incorrectly