⚡Flashcard Drill➔
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

  1. This is a 2-D 0/1 knapsack: each string consumes some zeros and some ones.
  2. dp[z][o] is the largest subset size using at most z zeros and o ones.
  3. For each string with zc zeros and oc ones, iterate z and o in descending order to avoid reusing the string.
  4. 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.count is concise and fast.
  • Swapping the two capacities: m limits zeros and n limits 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems