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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →