NeetCode #729LC-474Medium2-D Dynamic Programming
← Back to All Problems#729 · #474 · Ones and Zeroes(一和零)
📌 Problem Statement & Constraints
Given an array of binary strings
strs and integers m and n, find the largest subset that contains at most m zeros and at most n ones in total. Constraints: 1 <= strs.length <= 600, 1 <= strs[i].length <= 100, 1 <= m, n <= 100.💡 Core Algorithmic Approaches
- This is a 2-D 0/1 knapsack: each string consumes some zeros and some ones.
dp[z][o]is the largest subset size using at mostzzeros andoones.- For each string with
zczeros andocones, iteratezandoin descending order to avoid reusing the string. - The transition is
dp[z][o] = max(dp[z][o], dp[z-zc][o-oc] + 1).
💻 Benchmark Python3 Implementation
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
zc = s.count("0")
oc = len(s) - zc
for z in range(m, zc - 1, -1): # descending -> use once
for o in range(n, oc - 1, -1):
dp[z][o] = max(dp[z][o], dp[z - zc][o - oc] + 1)
return dp[m][n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(len(strs) * m * n): one 2-D knapsack update per string.
💾 Space Complexity
O(m * n): the 2-D DP table.
⚠️ Interview Pitfalls & Follow-ups
- Iterating the capacities ascending: that would allow the same string to be used repeatedly.
- Counting zeros with a manual loop: the built-in
s.countis concise and fast. - Swapping the two capacities:
mlimits zeros andnlimits ones, so mixing them up gives wrong bounds. - Treating it as a 1-D knapsack: both resources are constrained, so the state is genuinely 2-D.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.