474. Ones and Zeroes LeetCode Solution

In this guide, you will get 474. Ones and Zeroes LeetCode Solution with the best time and space complexity. The solution to Ones and Zeroes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Ones and Zeroes solution in C++
Ones and Zeroes solution in Java
Ones and Zeroes solution in Python
Additional Resources

474. Ones and Zeroes LeetCode Solution image

Problem Statement of Ones and Zeroes

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 <= 600
1 <= strs[i].length <= 100
strs[i] consists only of digits '0' and '1'.
1 <= m, n <= 100

Complexity Analysis

Time Complexity: O(kl \cdot mn), where k = |\texttt{strs}| and l = \max(|\texttt{strs[i]}|)
Space Complexity: O(mn)

474. Ones and Zeroes LeetCode Solution in C++

class Solution {
 public:
  int findMaxForm(vector<string>& strs, int m, int n) {
    // dp[i][j] := the maximum size of the subset given i 0s and j 1s are
    // available
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (const string& s : strs) {
      const int zeros = ranges::count(s, '0');
      const int ones = s.length() - zeros;
      for (int i = m; i >= zeros; --i)
        for (int j = n; j >= ones; --j)
          dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
    }

    return dp[m][n];
  }
};
/* code provided by PROGIEZ */

474. Ones and Zeroes LeetCode Solution in Java

class Solution {
  public int findMaxForm(String[] strs, int m, int n) {
    // dp[i][j] := the maximum size of the subset given i 0s and j 1s are
    // available
    int[][] dp = new int[m + 1][n + 1];

    for (final String s : strs) {
      final int zeros = (int) s.chars().filter(c -> c == '0').count();
      final int ones = (int) s.length() - zeros;
      for (int i = m; i >= zeros; --i)
        for (int j = n; j >= ones; --j)
          dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
    }

    return dp[m][n];
  }
}
// code provided by PROGIEZ

474. Ones and Zeroes LeetCode Solution in Python

class Solution:
  def findMaxForm(self, strs: list[str], m: int, n: int) -> int:
    # dp[i][j] := the maximum size of the subset given i 0s and j 1s are
    # available
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
      zeros = s.count('0')
      ones = len(s) - zeros
      for i in range(m, zeros - 1, -1):
        for j in range(n, ones - 1, -1):
          dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

    return dp[m][n]
 # code by PROGIEZ