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 function implementing the minimum falling path sum using bottom-up DP:

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

    for i in range(1, n):
        new_dp = [0]*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])
            new_dp[j] = matrix[i][j] + best
        dp = new_dp

    return min(dp)

matrix = [[2,1,3],[6,5,4],[7,8,9]]
print(minFallingPathSum(matrix))

What is the output of this code?

easy

A. 12

B. 13

C. 14

D. 15

Solution

1. Step 1: Trace dp after first row

   dp = [2, 1, 3]

2. Step 2: Compute dp for second row

   For i=1: - j=0: best = min(dp[0], dp[1]) = min(2,1) = 1 -> new_dp[0] = 6 + 1 = 7 - j=1: best = min(dp[1], dp[0], dp[2]) = min(1,2,3) = 1 -> new_dp[1] = 5 + 1 = 6 - j=2: best = min(dp[2], dp[1]) = min(3,1) = 1 -> new_dp[2] = 4 + 1 = 5 So new_dp = [7, 6, 5]

3. Step 3: Compute dp for third row

   For i=2: - j=0: best = min(new_dp[0], new_dp[1]) = min(7,6) = 6 -> new_dp[0] = 7 + 6 = 13 - j=1: best = min(new_dp[1], new_dp[0], new_dp[2]) = min(6,7,5) = 5 -> new_dp[1] = 8 + 5 = 13 - j=2: best = min(new_dp[2], new_dp[1]) = min(5,6) = 5 -> new_dp[2] = 9 + 5 = 14 So new_dp = [13, 13, 14]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Minimum of last dp row is 13 [OK]

Hint: Trace dp row by row, pick min at end [OK]

Common Mistakes:

• Off-by-one in indices
• Using old dp instead of new_dp values

2. You are given a grid where some cells are blocked and others are free. You need to find the number of unique paths from the top-left corner to the bottom-right corner, moving only down or right, but you cannot pass through blocked cells. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Dynamic Programming that builds solutions using previously computed subproblems while skipping blocked cells

B. Pure brute force recursion exploring all paths without memoization

C. Greedy algorithm that always moves right if possible, else down

D. Dijkstra's shortest path algorithm treating grid cells as graph nodes

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all unique paths avoiding obstacles, which involves overlapping subproblems and optimal substructure.

2. Step 2: Identify suitable algorithm

   Dynamic Programming efficiently computes the number of paths by reusing results and handling obstacles by zeroing paths through blocked cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles obstacles and overlapping subproblems correctly [OK]

Hint: DP handles obstacles and overlapping subproblems correctly [OK]

Common Mistakes:

• Thinking greedy can find all paths
• Using brute force without pruning
• Confusing shortest path with counting paths

3. Consider the following Python code implementing the space-optimized DP solution for counting unique paths with obstacles. Given the input grid below, what is the value of the dp array after processing the second row (i=1)? Input grid: [[0,0,0], [0,1,0], [0,0,0]]

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0]*n
    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
            else:
                if j > 0:
                    dp[j] += dp[j-1]
    return dp[-1]

easy

A. [1, 1, 1]

B. [1, 1, 0]

C. [1, 0, 0]

D. [1, 0, 1]

Solution

1. Step 1: Initialize dp after first row (i=0)

   dp starts as [1,0,0]. After processing first row (all zeros), dp updates to [1,1,1].

2. Step 2: Process second row (i=1)

   At j=0, obstacleGrid[1][0]=0, dp[0] remains 1.
   At j=1, obstacleGrid[1][1]=1 (obstacle), dp[1] set to 0.
   At j=2, obstacleGrid[1][2]=0, dp[2] += dp[1] -> dp[2] = 1 + 0 = 1.
   Resulting dp: [1, 0, 1]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp correctly zeroes obstacle cell and accumulates paths [OK]

Hint: Obstacles zero dp cells, dp[j] accumulates from dp[j-1] [OK]

Common Mistakes:

• Forgetting to zero dp[j] on obstacle
• Mis-updating dp[j] before dp[j-1]
• Confusing row and column indices

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

5. The following code attempts to compute the number of unique paths in an m x n grid using a space-optimized DP approach:

def uniquePaths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j]
    return dp[-1]

What is the bug in this code?

medium

A. Line 3 should start loop from 0 instead of 1

B. Line 4 incorrectly doubles dp[j] instead of adding dp[j-1]

C. Line 5 should return dp[0] instead of dp[-1]

D. Line 2 initializes dp with wrong size

Solution

1. Step 1: Analyze inner loop update

   Line 4 updates dp[j] by adding dp[j] to itself, doubling the value instead of adding dp[j-1].

2. Step 2: Identify correct update

   The correct update is dp[j] += dp[j - 1] to accumulate paths from left and top cells.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Doubling dp[j] breaks path count logic -> bug at line 4 [OK]

Hint: Check dp update uses dp[j-1], not dp[j] twice [OK]

Common Mistakes:

• Using dp[j] + dp[j] instead of dp[j] + dp[j-1]
• Off-by-one errors in loops