Ones and Zeroes - Solution & Explanation
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 0's and n 1's in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
Example 1:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
Example 2:
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.
Constraints:
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]consists only of digits'0'and'1'.1 <= m, n <= 100
Approach Overview
Problem Overview: You get an array of binary strings and two limits: m zeros and n ones. The task is to choose the largest subset of strings such that the total number of zeros used does not exceed m and the total number of ones does not exceed n.
The constraint immediately resembles a capacity problem. Each string “costs” a certain number of zeros and ones, and the goal is to maximize how many strings you include without exceeding those limits.
Approach 1: Memoized Recursive (Top-Down DP) (Time: O(k*m*n), Space: O(k*m*n))
Treat each string as a decision point: include it or skip it. First count how many zeros and ones the current string contains. Then recursively explore two choices: skip the string and move to the next index, or include it if the remaining capacity allows. Memoization stores results for states defined by (index, remainingZeros, remainingOnes). This prevents recomputation of overlapping subproblems.
The recursion behaves exactly like a 0/1 knapsack. Each string is an item with two resource costs. Memoization ensures every state is solved once, which keeps the runtime manageable. This approach is intuitive when thinking recursively and helps visualize the decision tree.
Approach 2: Dynamic Programming (0/1 Knapsack) (Time: O(k*m*n), Space: O(m*n))
The iterative dynamic programming version compresses the state into a 2D table dp[i][j], representing the maximum number of strings you can form using i zeros and j ones. For each string, compute its zero and one counts. Then iterate the DP table backwards (from m → zeros and n → ones) to update the state.
The reverse iteration is critical. It ensures each string is used at most once, preserving the 0/1 knapsack behavior. The update rule becomes: dp[i][j] = max(dp[i][j], 1 + dp[i-zeros][j-ones]). This approach eliminates the recursion stack and reduces memory from three dimensions to two.
This problem sits at the intersection of Dynamic Programming, Array, and String processing. The key step is converting each string into resource counts, which turns the problem into a classic capacity optimization.
Recommended for interviews: The bottom-up dynamic programming solution. Interviewers expect candidates to recognize the 0/1 knapsack pattern and build a 2D DP table with reverse iteration. Discussing the recursive memoized version first shows problem decomposition skills, while implementing the iterative DP demonstrates strong dynamic programming fundamentals.
Approach 1: Dynamic Programming Approach
This problem can be approached using a dynamic programming strategy similar to the knapsack problem. For each binary string, calculate the number of 0's and 1's it contains. Then, use a DP table to keep track of the maximum subset size you can achieve with a given count of 0's and 1's. We'll fill this table by iterating over each string and attempting to include it in our subset if the current capacity allows. Update the DP table in a reverse manner to avoid overwriting results prematurely.
In this C solution, we maintain a 2D array dp where dp[i][j] represents the maximum number of strings that can be formed with at most i zeros and j ones. For each binary string, we count zeros and ones, then update the DP table from back to front by considering if we include the current string in our subset. This ensures no overwriting of states that are yet to be calculated for the current iteration.
Complexity
Time Complexity: O(strsSize * m * n) where strsSize is the number of binary strings.
Space Complexity: O(m * n) for storing the DP table.
Approach 2: Memoized Recursive Approach
The problem can also be tackled using a recursive function with memoization to store already computed results and avoid redundant calculations. This approach uses recursion to consider two choices for each string - either include it in the subset or not, based on the available capacity for zeros and ones. By storing intermediate results, we can significantly reduce the number of recursive calls needed, thus optimizing the process.
This C implementation uses a recursive helper function with memoization. The function considers the inclusion and exclusion of each string in the subset while respecting the limits on zeros and ones. Using a 3-dimensional array, memoized results prevent duplicate work and improve efficiency.
Complexity
Time Complexity: O(strsSize * m * n) due to memoization.
Space Complexity: O(strsSize * m * n) for the memoization table.
Approach 3: Dynamic Programming
We define f[i][j][k] as the maximum number of strings that can be obtained from the first i strings using j zeros and k ones. Initially, f[i][j][k]=0, and the answer is f[sz][m][n], where sz is the length of the array strs.
For f[i][j][k], we have two choices:
- Do not select the
i-th string, in which casef[i][j][k]=f[i-1][j][k]; - Select the
i-th string, in which casef[i][j][k]=f[i-1][j-a][k-b]+1, whereaandbare the number of zeros and ones in thei-th string, respectively.
We take the maximum of these two choices to obtain the value of f[i][j][k].
The final answer is f[sz][m][n].
The time complexity is O(sz times m times n), and the space complexity is O(sz times m times n), where sz is the length of the array strs, and m and n are the upper limits on the number of zeros and ones, respectively.
Approach 4: Dynamic Programming (Space Optimization)
We notice that the calculation of f[i][j][k] only depends on f[i-1][j][k] and f[i-1][j-a][k-b]. Therefore, we can eliminate the first dimension and optimize the space complexity to O(m times n).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(strsSize * m * n) where strsSize is the number of binary strings. |
| Memoized Recursive Approach | Time Complexity: O(strsSize * m * n) due to memoization. |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Memoized Recursive (Top-Down DP) | O(k*m*n) | O(k*m*n) | When reasoning about include/exclude decisions is easier with recursion |
| Dynamic Programming (Bottom-Up Knapsack) | O(k*m*n) | O(m*n) | Best general solution; optimal memory usage and common interview expectation |
Video Solution
Ones and Zeroes - Leetcode 474 - Python • NeetCodeIO • 18,555 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Ones and Zeroes easy or hard?
How to solve Ones and Zeroes in O(k*m*n)?
What is the best approach for Ones and Zeroes?
What data structure is used in Ones and Zeroes?
What is the time complexity of Ones and Zeroes?
Ones and Zeroes Python or Java solution approach?
Is Ones and Zeroes asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Ones and Zeroes with our built-in code editor and test cases.
Practice on FleetCode