Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleFacebook

Ones and Zeroes (2D Knapsack)

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"strs":["10","0001","111001","1","0"],"m":5,"n":3}
Expected4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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}
⏱ 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.

Practice

(1/5)
1. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Greedy algorithm that repeatedly picks the largest element and tries to fit it into subsets
B. Dynamic programming with bitmask tabulation that tracks subset sums for all combinations
C. Simple backtracking without memoization that tries all possible assignments
D. Sorting the array and using a two-pointer technique to pair elements

Solution

  1. Step 1: Understand problem constraints

    The problem requires partitioning into equal sum subsets, which is a classic NP-complete problem requiring exploration of subsets.
  2. Step 2: Identify algorithmic pattern

    Dynamic programming with bitmask tabulation efficiently explores all subsets and tracks partial sums modulo target, guaranteeing optimality.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Bitmask DP covers all subsets systematically [OK]
Hint: Bitmask DP tracks all subset sums efficiently [OK]
Common Mistakes:
  • Assuming greedy always works for equal sum partition
  • Using backtracking without memoization leads to timeouts
2. What is the time complexity of the space-optimized bottom-up DP solution for Last Stone Weight II, where n is the number of stones and sum is the total weight of all stones?
medium
A. O(n + sum)
B. O(n^2)
C. O(n * sum * log n)
D. O(n * sum)

Solution

  1. Step 1: Identify loops in the code

    Outer loop runs n times (for each stone), inner loop runs up to half the total sum (sum/2).
  2. Step 2: Calculate total operations

    Each iteration updates dp array, so total operations ≈ n * (sum/2) -> O(n * sum).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    DP complexity depends on n and sum, not n squared or log factors [OK]
Hint: DP loops over stones and sums -> O(n * sum) [OK]
Common Mistakes:
  • Confusing n with sum leading to O(n^2)
  • Assuming logarithmic factor due to sorting
  • Ignoring that dp array size depends on sum
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. The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?
medium
A. Line 3: Missing base case assignment dp[0] = 0
B. Line 2: dp initialization with infinity
C. Line 5: Outer loop from 1 to n
D. Line 7: Inner loop condition j*j <= i

Solution

  1. Step 1: Identify base case importance

    dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.
  2. Step 2: Analyze impact of missing dp[0] = 0

    Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing dp[0] base case breaks DP initialization [OK]
Hint: dp[0] must be zero to start DP correctly [OK]
Common Mistakes:
  • Forgetting dp[0] initialization
  • Misplacing loop boundaries
5. What is the time complexity of the space-optimized bottom-up DP solution for the Target Sum problem with input array length n and total sum S = sum(nums)?
medium
A. O(2^n) because all sign combinations are explored
B. O(n * S) because the DP iterates over n elements and sums from -S to S
C. O(n^2) because of nested loops over elements
D. O(n * log S) due to binary search on sums

Solution

  1. Step 1: Identify loops in the DP

    The outer loop runs n times, the inner loop runs over sums from -S to S, total 2S+1 states.
  2. Step 2: Calculate total operations

    Each iteration updates dp for each sum, so total time is O(n * S). Exponential 2^n is brute force, not DP.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP complexity depends on n and sum range, not exponential [OK]
Hint: DP iterates over n and sum range, not all subsets [OK]
Common Mistakes:
  • Confusing brute force 2^n with DP complexity
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard