We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Ones and Zeroes

Number: 474

Difficulty: Medium

Paid? No

Companies: Uber, Google

Problem Description

Given an array of binary strings and two integers m and n, the goal is to determine the size of the largest subset of the array such that the subset contains at most m zeros and n ones. Essentially, you must choose a set of strings where the total number of '0's does not exceed m and the total number of '1's does not exceed n.

Key Insights

  • Recognize this problem as a 0/1 knapsack variant with two dimensions (number of zeros and ones acting as weight limits).
  • Use dynamic programming with a 2D dp array where dp[i][j] represents the maximum subset size achievable with i zeros and j ones.
  • Process each binary string by counting its zeros and ones, and update the dp array in reverse to avoid interference.
  • Using reverse iteration ensures that each string is considered only once (mimics the 0/1 knapsack pattern).

Space and Time Complexity

Time Complexity: O(l * m * n) where l is the number of strings, and m, n are the limits for zeros and ones respectively. Space Complexity: O(m * n) due to the 2D dp array used for dynamic programming.

Solution

We use a dynamic programming (DP) approach with a two-dimensional dp array of size (m+1) x (n+1). The entry dp[i][j] holds the maximum number of strings that can be included in the subset with at most i zeros and j ones. For each string in the array, count the number of zeros and ones. Then, update the dp state in reverse order to ensure that each string is used only once. This reverse update is crucial to prevent overcounting since each state depends on previous states before the string was considered. The algorithm ensures that by the end, dp[m][n] holds the size of the largest possible subset.

Code Solutions

# Python solution for Ones and Zeroes problem

def findMaxForm(strs, m, n):
    # Create a 2D DP array with dimensions (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Process each binary string in the list
    for binary_str in strs:
        count0 = binary_str.count('0')  # count zeros in the string
        count1 = binary_str.count('1')  # count ones in the string
        
        # Traverse the dp array in reverse order to avoid using the same string twice
        for zeros in range(m, count0 - 1, -1):
            for ones in range(n, count1 - 1, -1):
                # Decision: take max between not choosing and choosing the current string
                dp[zeros][ones] = max(dp[zeros][ones], dp[zeros - count0][ones - count1] + 1)
    
    return dp[m][n]

# Example usage:
if __name__ == '__main__':
    strs = ["10","0001","111001","1","0"]
    m = 5
    n = 3
    print(findMaxForm(strs, m, n))  # Expected output: 4
← Back to All Questions