Ones And Zeroes Leetcode Problem 474 [Python Solution]

The Ones And Zeroes Leetcode problem is categorized under the umbrella of 2-D Dynamic Programming and is considered to be of medium difficulty.

We’ll break down the problem, explore various solutions, and analyze their time and space complexities.

Problem Overview

The Ones And Zeroes problem involves working with an array of binary strings (strs) and two integers, m and n.

The goal is to determine the size of the largest subset of binary strings from strs such that the subset contains at most m 0’s and n 1’s.

The problem can be summarized as follows: Given a list of binary strings, you want to build a subset with the maximum number of strings while ensuring that the total count of 0’s in the subset does not exceed m, and the total count of 1’s does not exceed n.

Let’s illustrate this with an example:

Example:

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, which is greater than the maximum of 3.

The problem requires us to find the maximum size of a valid subset given the constraints.

Now, let’s dive into different approaches to solve this problem.

Understanding Constraints

Before we move on to the solutions, let’s understand the constraints of this problem:

• 1 <= strs.length <= 600: The input array can contain up to 600 binary strings.
• 1 <= strs[i].length <= 100: Each binary string in the array can have a length of up to 100 characters.
• strs[i] consists only of digits ‘0’ and ‘1’: The binary strings only contain ‘0’ and ‘1’.
• 1 <= m, n <= 100: The integers m and n represent the maximum number of 0’s and 1’s allowed in the subset.

Now that we’ve covered the problem statement and constraints, let’s explore different approaches to solving it.

Bruteforce Approach

A straightforward way to approach this problem is to use a recursive approach, considering each binary string one by one and making a decision to include it in the subset or not.

We’ll build a decision tree where each level of the tree corresponds to a binary string in the input array, and at each level, we make two choices: to include the string or skip it.

The base cases for our recursive function are as follows:

• If we go out of bounds (i.e., if the current index i exceeds the length of strs), we return 0 because there are no more strings to choose.
• If the result for the given parameters (i, m, n) is already computed (i.e., stored in a cache), we return the cached result.

Here’s the pseudocode for the recursive function:

def dfs(i, m, n):
    # Base cases
    if i == len(strs):
        return 0
    if (i, m, n) in dp:
        return dp[(i, m, n)]

    # Get the count of 0's and 1's in the current string
    mCnt, nCnt = strs[i].count("0"), strs[i].count("1")

    # Decision 1: Skip the current string
    result = dfs(i + 1, m, n)

    # Decision 2: Include the current string if possible
    if mCnt <= m and nCnt <= n:
        result = max(result, 1 + dfs(i + 1, m - mCnt, n - nCnt))

    # Cache the result and return it
    dp[(i, m, n)] = result
    return result


dp = {}
return dfs(0, m, n)

In this pseudocode, dfs is the recursive function, and dp is a cache used to store computed results to avoid redundant calculations.

We consider two choices for each string in strs: to skip it or to include it if it doesn’t violate the constraints.

The result is the maximum of these two choices.

This recursive approach explores all possible combinations, and the cached results ensure that we don’t recompute the same subproblems multiple times.

However, the time complexity is exponential, which makes it impractical for large inputs.

Time and Space Complexity

• Time Complexity: O(s * m * n), where s is the number of strings in strs.

The function dfs is called for each possible combination of i, m, and n.

The cache (dp) ensures that we don’t repeat the same calculations.

• Space Complexity: O(s * m * n), as we use a cache to store the results of subproblems.

Efficient Approach with Dynamic Programming

The brute force approach described above is not efficient for larger inputs due to its exponential time complexity.

To address this, we can use dynamic programming to optimize the solution.

We’ll build a 3D dynamic programming table to store the maximum size of the valid subset for different values of m and n.

Dynamic Programming Solution

We’ll create a 3D array dp, where dp[i][m][n] represents the maximum size of the valid subset for the first i binary strings, given that there are m zeros and n ones available.

Here’s the Python code for this dynamic programming solution:

def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # Create a 3D dynamic programming array
        dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)]

        for i in range(1, len(strs) + 1):
            # Get the count of 0's and 1's in the current string
            mCnt, nCnt = strs[i - 1].count("0"), strs[i - 1].count("1")

            for mRemaining in range(m + 1):
                for nRemaining in range(n + 1):
                    # Decision 1: Skip the current string
                    dp[i][mRemaining][nRemaining] = dp[i - 1][mRemaining][nRemaining]

                    # Decision 2: Include the current string if possible
                    if mRemaining >= mCnt and nRemaining >= nCnt:
                        dp[i][mRemaining][nRemaining] = max(
                            dp[i][mRemaining][nRemaining],
                            1 + dp[i - 1][mRemaining - mCnt][nRemaining - nCnt]
                        )

    # Return the maximum size of the valid subset
        return dp[len(strs)][m][n]

In this dynamic programming solution, we iteratively fill the dp array for each binary string in strs.

For each string, we consider two choices: to skip it or to include it in the subset.

We update the dp array based on these choices.

This approach eliminates the need for recursion and significantly improves the time complexity.

The time complexity is now O(s * m * n), where s is the number of strings in strs.

Reasoning Behind Our Efficient Approach

The dynamic programming approach improves the time complexity by efficiently computing and storing the results of subproblems.

It uses a 3D array to keep track of the maximum valid subset size for different values of m and n.

By considering each binary string one by one and updating the dp array, we can avoid redundant calculations and ensure that we find the maximum subset size.

Related Interview Questions By Company:

• Seat Reservation Manager LeetCode
• Rotate Image LeetCode
• Count Sub Islands LeetCode

Related Interview Questions By Difficulty:

• Burst Balloons LeetCode
• Best Time To Buy And Sell Stock With Cooldown LeetCode
• Longest Increasing Path In A Matrix LeetCode

Related Interview Questions By Category:

• Maximum Sum Circular Subarray LeetCode
• Plus One LeetCode
• Insert Interval LeetCode

Conclusion

In this blog post, we tackled the Ones And Zeroes problem from LeetCode.

We discussed the problem statement, constraints, and different approaches to solving it.

The dynamic programming approach provided an efficient solution, significantly improving the time complexity compared to the brute force approach.

By using dynamic programming, we can find the maximum size of a valid subset of binary strings while respecting the constraints on the number of 0’s and 1’s.

We encourage you to comment, ask questions, make suggestions, and share this content.

If you found this post helpful, please like and engage for more coding challenges and programming tutorials.

Question Link: Ones and Zeroes LeetCode Problem

Happy coding!