Ones and Zeroes: 2D Knapsack DP

You are given an array of binary strings and two integers m and n. Find the largest subset of strings such that the subset contains at most m zeros and n ones total across all selected strings.

This is LeetCode 474: Ones and Zeroes, and it is a clean example of the 2D 0/1 knapsack pattern. Instead of a single weight constraint like the classic knapsack, you have two constraints -- the zeros budget and the ones budget. Each string "costs" some zeros and some ones, and you want to maximize the count of strings you can pick without exceeding either budget.

Why this problem matters

Most DP knapsack problems have a single capacity dimension. Coin Change has one dimension (amount). Partition Equal Subset Sum has one dimension (target sum). This problem stretches the knapsack idea into two dimensions, which is a useful generalization to know.

The core concepts here are the same ones you have seen before:

• 0/1 constraint: each string is either included or not. No reuse.
• Optimal substructure: the best subset for budgets (i, j) depends on the best subsets for smaller budgets.
• Two-dimensional state: dp[i][j] tracks the max subset size with at most i zeros and j ones.

If you are comfortable with Partition Equal Subset Sum (1D 0/1 knapsack), this problem is the natural next step.

Counting costs

Before any DP, you need the cost of each string. For every string in the input, count its zeros and its ones.

def count(s):
    z = s.count('0')
    return z, len(s) - z

For the example strs = ["10", "0001", "111001", "1", "0"], the costs are:

• "10": 1 zero, 1 one
• "0001": 3 zeros, 1 one
• "111001": 2 zeros, 4 ones
• "1": 0 zeros, 1 one
• "0": 1 zero, 0 ones

With m = 5 and n = 3, you can fit "10", "0001", "1", and "0" for a total cost of 5 zeros and 3 ones. That is 4 strings, which is the maximum.

The DP formulation

Define dp[i][j] as the maximum number of strings you can select using at most i zeros and j ones. Initialize every cell to 0 (no strings selected yet).

For each string with cost (z, o):

• Iterate i from m down to z
• Iterate j from n down to o
• Update: dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1)

This is the same backward-iteration trick from 0/1 knapsack. You go from high to low so that each string is only counted once per pass. If you iterated forward, you could accidentally include the same string multiple times.

The only difference from the standard 0/1 knapsack is that you have two nested backward loops instead of one. The "take or skip" decision is identical.

The solution

def findMaxForm(strs, m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count('0')
        ones = len(s) - zeros
        for i in range(m, zeros - 1, -1):
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

    return dp[m][n]

That is it. The entire solution is a triple nested loop: one pass over each string, and two backward passes over the DP table. The structure is compact and follows directly from the recurrence.

Step-by-step walkthrough

Let's trace through a small example to see exactly how the table fills up.

Each string adds one more layer of possibilities. The backward iteration ensures that when you look up dp[i - z][j - o], it still reflects the state before including the current string. That is the 0/1 guarantee.

Why backward iteration matters

This is the same reasoning as in Partition Equal Subset Sum. If you iterated i from 0 up to m and j from 0 up to n, the updated cells from earlier iterations would be read by later iterations in the same pass. That would mean a single string could be "used" more than once, turning this into an unbounded knapsack instead of 0/1.

Going from m down to z and from n down to o ensures that you only read values from the previous round. Each string gets one shot at inclusion, exactly as the problem requires.

Complexity analysis

Where k is the number of strings. The DP table has (m + 1) * (n + 1) cells, and you iterate over it once per string. For the LeetCode constraints (k up to 600, m and n up to 100), that is 600 * 101 * 101 = roughly 6 million operations. Fast enough.

Edge cases to watch for

• Empty input: if strs is empty, return 0. The DP table stays all zeros.
• A string that exceeds both budgets: e.g., a string with 6 zeros when m = 5. The inner loops will not reach it (since zeros - 1 would be above m), so it is naturally skipped.
• All strings are "0" or all are "1": only one dimension matters. The DP still works, but you could solve it with simple counting.
• Single string: either it fits within (m, n) and the answer is 1, or it does not and the answer is 0.
• Budget of zero: if m = 0, you can only pick strings with no zeros (pure ones). If n = 0, you can only pick strings with no ones (pure zeros). If both are 0, the answer is 0 (only the empty string would fit, and it is not in the input).

The building blocks

This problem is built on take-or-skip DP, the same decision pattern as Partition Equal Subset Sum and Coin Change. At each string, you decide: include it (pay the cost, gain 1 toward the count) or skip it (move on with the same budget).

The structure:

• State: dp[i][j] = max strings selectable with at most i zeros and j ones
• Transition: for each string with cost (z, o), set dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1)
• Loop direction: backward on both dimensions (right to left, ensuring 0/1 constraint)

This same building block appears in other problems:

• Partition Equal Subset Sum (LeetCode 416): 1D 0/1 knapsack. Same backward loop, single dimension.
• Target Sum (LeetCode 494): another 0/1 knapsack variant with a twist on how the target is derived.
• Profitable Schemes (LeetCode 879): a harder 2D knapsack problem where you also need to meet a minimum profit threshold.

Once you see the 2D knapsack skeleton, these problems differ only in how the costs and values are defined.

From understanding to recall

The 2D knapsack pattern is not something you encounter every day, which makes it easy to forget. You might read this walkthrough and think "that makes sense," but blanking on the double backward loop when you see a similar problem a week from now is completely normal.

Spaced repetition helps bridge that gap. By revisiting the 2D DP table at increasing intervals and writing the nested loops from scratch each time, the pattern becomes automatic. The take-or-skip DP building block is one of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Drilling them individually beats random problem grinding every time.

Related posts

• Partition Equal Subset Sum -- The 1D version of 0/1 knapsack. Master this one first, then the 2D extension here feels natural.
• Coin Change -- Unbounded knapsack where the inner loop goes forward instead of backward. Good contrast with the 0/1 pattern used here.
• Combination Sum IV -- Another DP problem counting combinations under constraints, but with a different decision structure.