Skip to main content

474. Ones and Zeroes

medium

Pick the maximum number of binary strings such that the chosen subset uses at most m zeros and at most n ones. 2D knapsack — the two capacity dimensions are 'zeros consumed' and 'ones consumed'.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] consists only of digits '0' and '1'.
  • 1 <= m, n <= 100

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two-dimensional knapsack. State: (zeros remaining, ones remaining).

Hint 2

dp[i][j] = max number of strings selected using at most i zeros and j ones.

Hint 3

For each string with z zeros and o ones, sweep i from m down to z and j from n down to o: dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1).

Hint 4

Right-to-left sweep prevents reusing the current string in the same update.

Solution approach

Reveal approach

Bottom-up 2D knapsack. dp[i][j] is the maximum number of selected strings that consume at most i zeros and j ones. Initialize dp to all zeros. For each string in strs, count its zeros (z) and ones (o). Update dp in-place: sweep i from m down to z and j from n down to o, dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1). The right-to-left sweep over both dimensions ensures each string is considered at most once per subset. Return dp[m][n]. Time O(strs * m * n).

Complexity

Time
O(L * m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • knapsack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Ones and Zeroes and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →