Skip to main content

474 - Ones and Zeroes

Difficulty: Medium | Pattern: 2D Knapsack DP | Company tags: Google, Amazon

Problem Statement​

You are 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 0s and n 1s in the subset.

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: {"10","0001","1","0"} has 4 strings with 4 zeros and 3 ones.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2

Algorithm Flow​

Approach: 2D 0/1 Knapsack — O(mn × |strs|)​

Key insight: Standard 0/1 knapsack but with two "weights" (number of 0s and 1s). dp[i][j] = max subset size using at most i zeros and j ones.

def findMaxForm(strs: list[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for s in strs:
        zeros = s.count('0')
        ones = s.count('1')
        
        # Traverse in reverse to avoid reusing the same string
        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]

Dry Run​

strs = ["10","0","1"], m=1, n=1

Initial: dp = [[0,0],[0,0]]

Process "10" (zeros=1,ones=1):

  • i=1,j=1: dp[1][1] = max(0, dp[0][0]+1) = 1

Process "0" (zeros=1,ones=0):

  • i=1,j=1: dp[1][1] = max(1, dp[0][1]+1) = max(1,1) = 1
  • i=1,j=0: dp[1][0] = max(0, dp[0][0]+1) = 1

Process "1" (zeros=0,ones=1):

  • i=1,j=1: dp[1][1] = max(1, dp[1][0]+1) = max(1,2) = 2

Result: dp[1][1] = 2 ✓

Complexity​

  • Time: O(m × n × |strs|)
  • Space: O(m × n)

Key Terms​

TermDefinition
0/1 KnapsackDP pattern where each item is used at most once, subject to a capacity constraint.
Multi-dimensional DPA DP state indexed by more than one resource constraint (here: zeros used, ones used).
Reverse iterationLooping capacities from high to low so each item is only counted once per pass.
State transitionThe rule dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1) updating the DP table.

FAQ​

Q: Why must the inner loops iterate from m/n down to zeros/ones instead of upward? A: Forward iteration would let the same string be counted multiple times (like unbounded knapsack). Reverse iteration ensures each dp[i][j] update only uses values from before the current string was processed, enforcing the 0/1 (use-once) constraint.

Q: What is the space complexity, and can it be reduced further? A: Space is O(m × n) using the rolling 2D array (no extra dimension for the string index needed since we overwrite in place). It cannot easily go below O(m × n) since we need the full grid of achievable (zeros, ones) combinations.

Q: What if strs is empty? A: The DP table stays all zeros, and dp[m][n] correctly returns 0 — no changes needed to the algorithm.

Q: How does this differ from the classic 0/1 knapsack with a single weight? A: It's the same recurrence extended to two independent capacity dimensions; instead of one 1D array, you maintain a 2D array and decrement in both dimensions per item.

Q: Could a greedy approach (e.g., picking strings with fewest total characters first) work? A: No — greedy fails because optimal selection depends on the joint (zeros, ones) balance, not just the total character count; DP is required to explore all trade-offs correctly.

Quick Revision​

  • This is 0/1 knapsack with two capacities: number of 0s (m) and number of 1s (n).
  • dp[i][j] = max subset size using at most i zeros and j ones.
  • For each string, count its zeros/ones, then update dp in reverse order over both dimensions.
  • Reverse iteration is essential — it prevents reusing the same string twice.
  • Final answer is dp[m][n].
  • Time: O(m × n × |strs|); Space: O(m × n).
  • Empty strs or m=n=0 correctly yields 0.
  • Same recurrence pattern as single-dimension 0/1 knapsack, just with an extra loop.
  • Partition to K Equal Sum Subsets / Partition Equal Subset Sum — related knapsack-style subset selection.
  • 322 - Coin Change — single-dimension unbounded knapsack DP for contrast.
  • Target Sum — another DP problem reducible to a subset-sum / knapsack formulation.