Ones and Zeroes (2D Knapsack)

▶

Steps

setup

Initialize DP Table

Create a 2D dp array of size (m+1) x (n+1) filled with zeros, representing no strings chosen yet.

💡 Initialization sets the base case: with zero strings, the maximum subset size is zero regardless of zeros and ones available.

Line:

dp = [[0] * (n + 1) for _ in range(m + 1)]

💡 The dp table starts empty, ready to be filled as strings are processed.

setup

Process First String "10" - Count zeros and ones

Count zeros and ones in the first string "10": zeros=1, ones=1.

💡 Knowing the cost in zeros and ones for each string is essential to update the dp table correctly.

Line:

zeros = s.count('0')
ones = len(s) - zeros

💡 The first string requires 1 zero and 1 one to be included.

fill_cells

Update dp for "10" at i=5, j=3

Check if including "10" improves dp[5][3]. Compare dp[5][3] and 1 + dp[4][2].

💡 We try to include the string if it increases the maximum subset size for the given zeros and ones.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "10" increases the max subset size at dp[5][3] from 0 to 1.

fill_cells

Update dp for "10" at i=4, j=2

Check if including "10" improves dp[4][2]. Compare dp[4][2] and 1 + dp[3][1].

💡 We continue updating dp cells where resources allow including the string.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "10" increases dp[4][2] to 1.

fill_cells

Update dp for "10" at i=3, j=1

Check if including "10" improves dp[3][1]. Compare dp[3][1] and 1 + dp[2][0].

💡 We update dp cells moving downwards to avoid overwriting needed values.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "10" increases dp[3][1] to 1.

setup

Process Second String "0001" - Count zeros and ones

Count zeros and ones in "0001": zeros=3, ones=1.

💡 We prepare to update dp with the next string's resource costs.

Line:

zeros = s.count('0')
ones = len(s) - zeros

💡 The second string requires 3 zeros and 1 one to be included.

fill_cells

Update dp for "0001" at i=5, j=3

Check if including "0001" improves dp[5][3]. Compare dp[5][3] and 1 + dp[2][2].

💡 We try to include the second string if it increases the max subset size.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "0001" does not increase dp[5][3] beyond current max 1.

fill_cells

Update dp for "0001" at i=4, j=2

Check if including "0001" improves dp[4][2]. Compare dp[4][2] and 1 + dp[1][1].

💡 We continue updating dp cells where resources allow including the string.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "0001" does not increase dp[4][2] beyond current max 1.

fill_cells

Update dp for "0001" at i=3, j=1

Check if including "0001" improves dp[3][1]. Compare dp[3][1] and 1 + dp[0][0].

💡 We update dp cells moving downwards to avoid overwriting needed values.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "0001" does not increase dp[3][1] beyond current max 1.

setup

Process Third String "111001" - Count zeros and ones

Count zeros and ones in "111001": zeros=2, ones=4.

💡 We prepare to update dp with the next string's resource costs.

Line:

zeros = s.count('0')
ones = len(s) - zeros

💡 The third string requires 2 zeros and 4 ones, which exceeds the ones limit n=3.

prune

Skip updates for "111001" due to ones > n

Since ones=4 > n=3, no dp cells can be updated for this string.

💡 Strings that require more ones than available cannot be included, so dp remains unchanged.

Line:

for i in range(m, zeros - 1, -1):
    for j in range(n, ones - 1, -1):
        ... (no iterations since ones > n)

💡 The dp table remains unchanged after considering this string.

setup

Process Fourth String "1" - Count zeros and ones

Count zeros and ones in "1": zeros=0, ones=1.

💡 We prepare to update dp with the next string's resource costs.

Line:

zeros = s.count('0')
ones = len(s) - zeros

💡 The fourth string requires 0 zeros and 1 one to be included.

fill_cells

Update dp for "1" at i=5, j=3

Check if including "1" improves dp[5][3]. Compare dp[5][3] and 1 + dp[5][2].

💡 We try to include the string if it increases the max subset size.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "1" does not increase dp[5][3] beyond current max 1.

fill_cells

Update dp for "1" at i=5, j=2

Check if including "1" improves dp[5][2]. Compare dp[5][2] and 1 + dp[5][1].

💡 We continue updating dp cells where resources allow including the string.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "1" increases dp[5][2] to 1.

fill_cells

Update dp for "1" at i=5, j=1

Check if including "1" improves dp[5][1]. Compare dp[5][1] and 1 + dp[5][0].

💡 We update dp cells moving downwards to avoid overwriting needed values.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "1" increases dp[5][1] to 1.

setup

Process Fifth String "0" - Count zeros and ones

Count zeros and ones in "0": zeros=1, ones=0.

💡 We prepare to update dp with the last string's resource costs.

Line:

zeros = s.count('0')
ones = len(s) - zeros

💡 The fifth string requires 1 zero and 0 ones to be included.

fill_cells

Update dp for "0" at i=5, j=3

Check if including "0" improves dp[5][3]. Compare dp[5][3] and 1 + dp[4][3].

💡 We try to include the string if it increases the max subset size.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "0" does not increase dp[5][3] beyond current max 1.

fill_cells

Update dp for "0" at i=4, j=3

Check if including "0" improves dp[4][3]. Compare dp[4][3] and 1 + dp[3][3].

💡 We continue updating dp cells where resources allow including the string.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "0" increases dp[4][3] to 1.

fill_cells

Update dp for "0" at i=3, j=3

Check if including "0" improves dp[3][3]. Compare dp[3][3] and 1 + dp[2][3].

💡 We update dp cells moving downwards to avoid overwriting needed values.

Line:

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

💡 Including "0" increases dp[3][3] to 1.

reconstruct

Final Answer Read from dp[m][n]

Return dp[5][3] which is the maximum number of strings that can be formed with 5 zeros and 3 ones.

💡 The final dp cell contains the answer to the problem.

Line:

return dp[m][n]

💡 The maximum subset size is 4, as dp[5][3] = 4 after all updates.

from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # STEP 1

    for idx, s in enumerate(strs):  # STEP 2,6,10,12,16
        zeros = s.count('0')  # STEP 2,6,10,12,16
        ones = len(s) - zeros  # STEP 2,6,10,12,16
        for i in range(m, zeros - 1, -1):  # STEP 3-5,7-9,13-15,17-19
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])  # STEP 3-5,7-9,13-15,17-19

    return dp[m][n]  # STEP 20

if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4

📊

Ones and Zeroes (2D Knapsack) - Watch the Algorithm Execute, Step by Step

Watching the dp table fill in real time reveals how the algorithm balances the two constraints and builds up the solution incrementally.

Initializing dp array

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

initialized to 0

Item 0 - wt:1 val:1

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

Item 0 - wt:1 val:1

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

updated

Item 0 - wt:1 val:1

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

updated

Item 0 - wt:1 val:1

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

updated

Item 1 - wt:3 val:1

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

Item 1 - wt:3 val:1

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

no change

Item 1 - wt:3 val:1

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

no change

Item 1 - wt:3 val:1

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

no change

Item 2 - wt:2 val:4

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

Item 2 - wt:2 val:4

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

Item 3 - wt:0 val:1

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

Item 3 - wt:0 val:1

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

no change

Item 3 - wt:0 val:1

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

updated

Item 3 - wt:0 val:1

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

updated

Item 4 - wt:1 val:0

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

Item 4 - wt:1 val:0

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

no change

Item 4 - wt:1 val:0

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

updated

Item 4 - wt:1 val:0

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

updated

Initializing dp array

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

final answer

Key Takeaways

✓ The dp table incrementally builds the maximum subset size respecting two constraints simultaneously.

This insight is hard to see from code alone because the two-dimensional resource constraints and their interaction are subtle.

✓ The dp table is filled in reverse order of zeros and ones to avoid overwriting values needed for future computations.

Watching the fill order visually clarifies why the loops go backwards, which is not obvious from code.

✓ Strings that require more zeros or ones than available are pruned automatically, leaving dp unchanged for those cases.

Seeing no updates for such strings helps understand how resource constraints prune the search space.

Practice

1. Consider the following code snippet implementing the minimum cost for tickets problem. What is the value of dp[0] after the loop completes for the input days = [1,4,6] and costs = [2,7,15]?

easy

A. 6

B. 7

C. 9

D. 4

Solution

1. Step 1: Trace dp from the end

   dp[3] = 0 (base case). For i=2 (day=6): - 1-day ticket: cost=2 + dp[3]=2 - 7-day ticket: cost=7 + dp[3]=7 - 30-day ticket: cost=15 + dp[3]=15 Minimum = 2 -> dp[2]=2

2. Step 2: Calculate dp[1] and dp[0]

   i=1 (day=4): - 1-day: cost=2 + dp[2]=4 - 7-day: cost=7 + dp[3]=7 - 30-day: cost=15 + dp[3]=15 Minimum=4 -> dp[1]=4 i=0 (day=1): - 1-day: cost=2 + dp[1]=6 - 7-day: cost=7 + dp[3]=7 - 30-day: cost=15 + dp[3]=15 Minimum=6 -> dp[0]=6

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[0] correctly computed as 6 [OK]

Hint: Trace dp from end to start carefully [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Miscomputing next_i with bisect
• Confusing costs and dp sums

2. The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?

def integer_break(n):
    dp = [0] * n
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

medium

A. Line 3: dp[1] = 1 base case initialization

B. Line 2: dp array size is n instead of n+1

C. Line 5: Outer loop range from 2 to n+1

D. Line 7: Using max(j, dp[j]) instead of just dp[j]

Solution

1. Step 1: Check dp array size

   dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.

2. Step 2: Consequences of wrong size

   Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp array must be size n+1 to safely index up to n [OK]

Hint: Check array size matches max index accessed [OK]

Common Mistakes:

• Forgetting dp size off-by-one
• Misplacing base case initialization

3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for counting the number of ways to make change with n coins and amount W?

medium

A. O(n * W) because for each coin we iterate over all amounts up to W

B. O(n + W) because we iterate over coins and amounts separately

C. O(W^n) due to nested loops over coins and amounts

D. O(n * W) plus O(W) auxiliary space for the dp array

Solution

1. Step 1: Identify loops and their ranges

   Outer loop runs n times (coins), inner loop runs up to W (amount), so time is O(n * W).

2. Step 2: Consider space usage

   DP array size is W+1, so auxiliary space is O(W). Total complexity includes both time and space, but time complexity is the main focus here.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time O(n*W) matches DP approach [OK]

Hint: Time is product of coins and amount; space is dp array size [OK]

Common Mistakes:

• Confusing time with space complexity
• Forgetting auxiliary space for dp array
• Mistaking exponential complexity for DP

4. The following code attempts to solve the Partition to K Equal Sum Subsets problem using DP with bitmask tabulation. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.

def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0

medium

A. Line: dp = [-1] * (1 << n)

B. Line: if dp[next_mask] == -1: (missing in this code)

C. Line: nums.sort()

D. Line: dp[next_mask] = (dp[mask] + nums[i]) % target

Solution

1. Step 1: Identify missing condition

   The code lacks a check if dp[next_mask] is already set, so it overwrites states, causing incorrect results.

2. Step 2: Pinpoint the buggy line

   The line assigning dp[next_mask] unconditionally overwrites previous valid states, breaking memoization.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding "if dp[next_mask] == -1:" before assignment fixes bug [OK]

Hint: Always check if dp state is unset before assignment [OK]

Common Mistakes:

• Overwriting dp states without checking leads to incorrect answers
• Not pruning symmetric states increases runtime

5. Suppose the problem is modified so that each element in the array can be used multiple times (unlimited reuse) to form k equal sum subsets. Which of the following modifications to the DP with bitmask tabulation approach correctly adapts to this change?

hard

A. Use backtracking with memoization on subsets but do not use bitmasking since reuse breaks subset uniqueness

B. Keep the same bitmask DP but allow setting dp[next_mask] multiple times without restriction

C. Replace bitmask DP with a classic unbounded knapsack DP that tracks sums without bitmasking

D. Modify the bitmask DP to reset dp states after each full subset sum is reached to allow reuse

Solution

1. Step 1: Understand reuse impact

   Allowing unlimited reuse breaks the uniqueness assumption of subsets represented by bitmasks.

2. Step 2: Identify suitable DP approach

   Classic unbounded knapsack DP tracks sums without bitmasking, correctly handling reuse.

3. Step 3: Evaluate other options

   Bitmask DP relies on unique element usage; modifying it without removing bitmasking leads to incorrect states.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Unbounded knapsack DP handles reuse correctly [OK]

Hint: Bitmask DP assumes unique usage; reuse needs unbounded knapsack DP [OK]

Common Mistakes:

• Trying to reuse bitmask DP without removing uniqueness assumption
• Ignoring that reuse breaks subset partitioning logic