Ones and Zeroes Easy 0 attempts
LeetCode ↗

Ones and Zeroes

Easy Dynamic ProgrammingMemoization LeetCode

Given an array of binary strings and limits m zeros and n ones, return the max number of strings that can be formed within the limits.

Example: strs = ["10","0001","111001","1","0"], m=5, n=3 → Output: 4

Sample Input
—
Sample Output
—
Constraints
  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • 1 <= m, n <= 100
Test Cases
Case 1
Args: [["10","0001","111001","1","0"],5,3] Expected: 4
Topics
Dynamic ProgrammingMemoization

2D Knapsack DP

function findMaxForm(strs, m, n) {
  const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
  for (const s of strs) {
    const zeros = [...s].filter(c => c==='0').length;
    const ones = s.length - zeros;
    for (let i = m; i >= zeros; i--)
      for (let j = n; j >= ones; j--)
        dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
  }
  return dp[m][n];
}

Time: O(L × m × n) | Space: O(m × n)

Saved in this browser only. Private to you.

JavaScript