Ones and Zeroes (2D Knapsack)

📋

Problem

Imagine you have a collection of binary strings and a limited number of 0s and 1s you can use. How do you pick the maximum number of strings without exceeding your 0s and 1s budget?

Given an array of binary strings strs and two integers m and n, return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset. Each 0 and 1 can only be used once across the chosen subset.

1 ≤ strs.length ≤ 6001 ≤ strs[i].length ≤ 1001 ≤ m, n ≤ 100

Edge cases: Empty strs array → output 0m = 0 and n = 0 → output 0 since no zeros or ones can be usedAll strings contain only zeros → output limited by m

</>

IDE

def findMaxForm(strs: List[str], m: int, n: int) -> int:public int findMaxForm(String[] strs, int m, int n)int findMaxForm(vector<string>& strs, int m, int n)function findMaxForm(strs, m, n)

def findMaxForm(strs, m, n):
    # Write your solution here
    pass

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findMaxForm(vector<string>& strs, int m, int n) {
    // Write your solution here
    return 0;
}

function findMaxForm(strs, m, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 5Greedy approach picking all strings with fewer zeros or ones without capacity checks.✅ Implement 0/1 knapsack DP with reverse iteration over capacities to avoid overcounting.

Wrong: 3Treating problem as unbounded knapsack allowing multiple picks of same string.✅ Iterate dp arrays in reverse order to enforce single pick per string.

Wrong: 1Off-by-one errors in dp indexing causing missed valid states.✅ Carefully iterate dp from capacity down to zeros/ones counts, checking boundaries.

Wrong: Non-zero for empty inputMissing base case for empty input array.✅ Return 0 immediately if input array is empty.

Wrong: Non-zero when m=0 and n=0Ignoring capacity constraints when zero capacity.✅ Return 0 if m == 0 and n == 0 regardless of input.

✓

Test Cases

Focus on handling empty inputs and zero capacity edge cases correctly.

Watch out for common algorithmic traps like greedy selection or unbounded knapsack confusion.

Optimize your DP solution to run efficiently on large inputs.

t1_01basic

Input{"strs":["10","0001","111001","1","0"],"m":5,"n":3}

Expected4

⏱ Performance - must finish in 2000ms

We can form the subset {"10", "0001", "1", "0"} which uses 5 zeros and 3 ones in total.

💡 Think about counting zeros and ones for each string and using a 2D DP table for capacity.

💡 Use a bottom-up DP approach with dimensions m+1 and n+1 to track max subset size.

💡 Update dp[w][k] = max(dp[w][k], 1 + dp[w - zeros][k - ones]) when zeros <= w and ones <= k.

Why it failed: Basic case failed - likely incorrect DP state update or ignoring capacity constraints. Fix by ensuring dp updates only when zeros and ones fit within m and n.

✓ Core recurrence and capacity checks implemented correctly.

t1_02basic

Input{"strs":["0","1","10","11","000"],"m":3,"n":2}

Expected4

⏱ Performance - must finish in 2000ms

Subset {"0", "1", "10", "000"} uses 3 zeros and 2 ones, maximizing count to 4.

💡 Count zeros and ones per string and consider all subsets with DP.

💡 Remember to update dp in reverse order to avoid reuse of the same string multiple times.

💡 Check dp[w][k] = max(dp[w][k], 1 + dp[w - zeros][k - ones]) only if zeros <= w and ones <= k.

Why it failed: Failed to handle multiple strings with overlapping zeros and ones counts or reused strings incorrectly. Fix by iterating dp in reverse order to enforce 0/1 knapsack constraints.

✓ Correctly handles multiple strings and capacity constraints.

t2_01edge

Input{"strs":[],"m":5,"n":3}

Expected0

⏱ Performance - must finish in 2000ms

Empty input array means no strings to choose, so max subset size is 0.

💡 Check how your code handles empty input arrays.

💡 Make sure base case returns 0 when no strings are available.

💡 Return 0 immediately if strs is empty.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding base case to return 0 when strs is empty.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"strs":["0"],"m":0,"n":0}

Expected0

⏱ Performance - must finish in 2000ms

No zeros or ones allowed, so cannot pick any string even if it contains only zeros or ones.

💡 Check boundary conditions when m and n are zero.

💡 Ensure no strings are chosen if capacity is zero.

💡 Return 0 if m == 0 and n == 0 regardless of input strings.

Why it failed: Incorrectly picks strings when m and n are zero. Fix by enforcing capacity constraints strictly.

✓ Correctly returns 0 when no capacity is available.

t2_03edge

Input{"strs":["0","00","000"],"m":2,"n":5}

Expected2

⏱ Performance - must finish in 2000ms

Only zeros matter here; can pick "0" and "00" using 3 zeros total, but m=2 limits to max 2 zeros, so max subset size is 2 by picking "0" and "00" (only full strings can be chosen).

💡 Consider strings with only zeros and how m limits selection.

💡 Count zeros carefully and ensure dp respects zero capacity.

💡 Pick strings whose total zeros do not exceed m.

Why it failed: Fails to limit selection by zero capacity m. Fix by checking zeros count against m before updating dp.

✓ Correctly limits selection by zero capacity.

t3_01corner

Input{"strs":["10","01","10","01"],"m":2,"n":2}

Expected2

⏱ Performance - must finish in 2000ms

Greedy approach picking strings with fewer zeros or ones fails; correct max subset is 2 by picking any two strings fitting capacity.

💡 Beware of greedy approaches that pick strings based on zeros or ones count alone.

💡 Use DP to consider all combinations rather than greedy selection.

💡 Update dp in reverse order to avoid reusing strings.

Why it failed: Greedy approach overcounts by picking more strings than capacity allows. Fix by implementing 0/1 knapsack DP with reverse iteration.

✓ DP correctly handles greedy trap and capacity constraints.

t3_02corner

Input{"strs":["0","0","0","0"],"m":2,"n":2}

Expected2

⏱ Performance - must finish in 2000ms

Confusing 0/1 knapsack with unbounded knapsack leads to picking more than allowed; max subset is 2 due to m=2 zeros capacity.

💡 Distinguish 0/1 knapsack from unbounded knapsack: each string can be chosen at most once.

💡 Iterate dp in reverse order to prevent multiple picks of the same string.

💡 Check capacity constraints strictly for each string.

Why it failed: Mistakenly treats problem as unbounded knapsack, allowing multiple picks of same string. Fix by iterating dp in reverse order.

✓ Correctly enforces 0/1 knapsack constraints.

t3_03corner

Input{"strs":["1","0","10","01"],"m":1,"n":1}

Expected2

⏱ Performance - must finish in 2000ms

Off-by-one errors in capacity indexing cause incorrect results; max subset is 2 by picking "1" and "0" or "10" alone.

💡 Check indexing carefully when updating dp arrays.

💡 Ensure capacity indices do not go out of bounds.

💡 Use dp[w][k] with w and k from m down to zeros and ones respectively.

Why it failed: Off-by-one errors cause dp to access invalid indices or skip valid states. Fix by careful reverse iteration and boundary checks.

✓ Correct indexing and boundary handling in dp.

t4_01performance

Input{"strs":["0","1","10","01","110","001","111","000","101","010","11","00","100","011","1110","0001","1010","0101","1100","0011","1111","0000","1011","0110","1101","0010","1001","0100","11100","00011","10101","01010","11011","00100","10010","01101","11110","00001","10110","01011","11001","00110","10011","01110","11101","00010","10100","01001","11010","00101","11111","00000","10111","01111","11011","00111","10011","01011","11101","00011","10101","01001","11001","00101","10001","01101","11100","00010","10110","01010","11010","00110","10010","01110","11110","00010","10100","01000","11000","00100","10000","01000","11111","00000","10101","01101","11001","00101","10001","01001","11110","00010","10110","01010","11010","00110","10010","01110","11100","00010"],"m":100,"n":100}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 strings, m=100 zeros capacity, n=100 ones capacity; O(l*m*n) DP must complete within 2 seconds.

💡 DP complexity is O(l*m*n) where l = number of strings.

💡 Avoid exponential brute force; use bottom-up DP with 2D capacity arrays.

💡 Optimize by iterating dp in reverse order to enforce 0/1 knapsack constraints.

Why it failed: TLE due to exponential brute force or inefficient recursion without memoization. Fix by implementing bottom-up DP with O(l*m*n) complexity.

✓ Efficient DP solution runs within time limits.

Practice

1. You are given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. You want to maximize the total value of items placed in the knapsack without exceeding its capacity. Which algorithmic approach guarantees finding the optimal solution for this problem?

easy

A. A greedy algorithm that picks items with the highest value-to-weight ratio first.

B. Dynamic programming that considers including or excluding each item for every capacity up to the maximum.

C. A simple recursive approach without memoization that tries all subsets of items.

D. A breadth-first search exploring all possible combinations of items.

Solution

1. Step 1: Understand problem constraints and overlapping subproblems

   The problem requires maximizing value without exceeding capacity, which is a classic optimization problem with overlapping subproblems suitable for dynamic programming.

2. Step 2: Identify algorithmic approach that guarantees optimality

   Greedy algorithms fail because picking locally optimal items (highest value/weight) does not guarantee global optimum. Exhaustive search is correct but inefficient. Dynamic programming systematically explores all item inclusion/exclusion states with memoization, ensuring optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP solves 0/1 Knapsack optimally by exploring all states [OK]

Hint: DP with inclusion/exclusion ensures optimal solution [OK]

Common Mistakes:

• Greedy approach works for fractional knapsack, not 0/1 knapsack.

2. You are given a list of positive integers and a target sum. You need to determine if there exists a subset of these integers that sums exactly to the target. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A greedy algorithm that picks the largest numbers first until the sum is reached or exceeded.

B. A dynamic programming approach that builds a boolean table tracking achievable sums up to the target.

C. A depth-first search that tries all subsets without memoization.

D. A sorting-based two-pointer technique to find pairs that sum to the target.

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if any subset sums exactly to a target, which is a classic subset sum problem.

2. Step 2: Identify algorithm that guarantees correctness

   Greedy and two-pointer approaches fail because they do not consider all subsets. DFS without memoization is correct but inefficient. Dynamic programming builds a table of achievable sums, ensuring all subsets are considered efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP tracks all sums up to target -> correct [OK]

Hint: Subset sum requires DP to track achievable sums [OK]

Common Mistakes:

• Thinking greedy or sorting solves subset sum optimally

3. Consider the following buggy code for lastStoneWeightII. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line 4: dp[0] = true is missing

B. Line 7: Outer loop over stones

C. Line 8: Inner loop iterates backwards

D. Line 10: Return statement calculation

Solution

1. Step 1: Identify dp initialization

   dp[0] must be true to represent sum zero achievable with no stones; missing this means no sums are marked achievable.

2. Step 2: Consequence of missing dp[0] = true

   Without dp[0] = true, dp array remains false, so no sums can be formed, causing the function to fail to find any valid partition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initializing dp[0] is critical base case for subset sum DP [OK]

Hint: dp[0] = true is base case for subset sums [OK]

Common Mistakes:

• Forgetting dp[0] initialization
• Iterating forward in inner loop causing double counting
• Miscomputing return value

4. What is the time complexity of the bottom-up dynamic programming solution for the Perfect Squares problem using the unbounded knapsack pattern, where n is the input number?

medium

A. O(n^2)

B. O(sqrt(n) * log n)

C. O(n * log n)

D. O(n * sqrt(n))

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop runs from 1 to n (O(n)). The inner loop iterates over all perfect squares less than or equal to i, which is approximately O(sqrt(n)) because the largest square root is about sqrt(n).

2. Step 2: Combine complexities

   Multiplying outer and inner loops gives O(n * sqrt(n)). Other options either overestimate (O(n^2)) or underestimate (O(n log n), O(sqrt(n) log n)) the complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops: n and sqrt(n) -> O(n * sqrt(n)) [OK]

Hint: Inner loop runs up to sqrt(n), outer up to n [OK]

Common Mistakes:

• Assuming inner loop is O(n)
• Confusing recursion stack space with DP space

5. Suppose the Target Sum problem is modified so that each number in the array can be used multiple times (unlimited reuse). Which of the following changes correctly adapts the DP solution to this variant?

hard

A. Use a 1D dp array and update dp in forward order for each num to allow reuse

B. Keep the same DP with offset and update dp in reverse order to avoid double counting

C. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num]

D. Switch to a brute force recursion since DP cannot handle reuse

Solution

1. Step 1: Understand reuse impact on DP iteration

   Allowing unlimited reuse means for each num, dp must be updated in forward order so that dp[s-num] includes ways using current num multiple times.

2. Step 2: Identify correct DP update order

   Backward iteration prevents reuse by only using previous states. Forward iteration accumulates counts correctly for unlimited usage.

3. Step 3: Evaluate options

   Use a 1D dp array and update dp in forward order for each num to allow reuse correctly updates dp forward. Keep the same DP with offset and update dp in reverse order to avoid double counting backward iteration is for no reuse. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num] restricts to previous items only. Switch to a brute force recursion since DP cannot handle reuse is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward dp update enables multiple usage of same number [OK]

Hint: Forward dp iteration enables unlimited reuse [OK]

Common Mistakes:

• Using backward iteration which forbids reuse