Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleFacebook

Ones and Zeroes (2D Knapsack)

Choose your preparation mode4 modes available
🎯
Ones and Zeroes (2D Knapsack)
mediumDPAmazonGoogleFacebook

Imagine you have a collection of binary strings and a limited number of 0s and 1s you can use. How do you pick the maximum number of strings without exceeding your 0s and 1s budget?

💡 This problem is a classic example of a 2D knapsack variant where instead of one weight constraint, we have two constraints (count of zeros and ones). Beginners often struggle because it extends the classic knapsack problem to two dimensions, making brute force solutions explode exponentially and requiring careful dynamic programming to optimize.
📋
Problem Statement

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. Each 0 and 1 can only be used once across the chosen subset.

1 ≤ strs.length ≤ 6001 ≤ strs[i].length ≤ 1001 ≤ m, n ≤ 100
💡
Example
Input"strs = [\"10\", \"0001\", \"111001\", \"1\", \"0\"], m = 5, n = 3"
Output4

We can form the subset {"10", "0001", "1", "0"} which uses 5 zeros and 3 ones in total.

  • Empty strs array → output 0
  • m = 0 and n = 0 → output 0 since no zeros or ones can be used
  • All strings contain only zeros → output limited by m
  • All strings contain only ones → output limited by n
🔁
Why DP?
Why greedy fails:

A greedy approach that picks strings with the least zeros or ones first can fail. For example, picking many small strings with few zeros but many ones might prevent choosing a larger string that fits better overall, leading to suboptimal subsets.

DP state:

dp[i][j] represents the maximum number of strings that can be formed using at most i zeros and j ones from the strings considered so far.

Recurrence:dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) if i >= zeros and j >= ones

For each string, either skip it or include it if enough zeros and ones remain, updating dp accordingly.

⚠️
Common Mistakes
Iterating dp array forwards instead of backwards

Strings get counted multiple times, leading to incorrect results

✅ Iterate zeros and ones backwards when updating dp

Not counting zeros and ones correctly

Incorrect feasibility checks cause wrong dp updates

✅ Carefully count zeros and ones for each string before dp update

Not handling base cases in recursion

Stack overflow or incorrect results

✅ Return 0 when index reaches end of strings

Using mutable default arguments in recursion (Python)

Unexpected shared state across calls

✅ Avoid mutable defaults or use memo dict explicitly

🧠
Brute Force (Pure Recursion)
💡 Starting with brute force helps understand the problem's exponential nature and the need for optimization. It lays the foundation for memoization and DP.

Intuition

Try every subset of strings, recursively deciding to include or exclude each string, and track zeros and ones used.

Algorithm

  1. Define a recursive function that takes the current index and remaining zeros and ones.
  2. If index is beyond last string, return 0.
  3. For current string, count zeros and ones.
  4. If enough zeros and ones remain, recurse including the string and excluding it, take max.
  5. Return the maximum count found.
💡 The recursion tree grows exponentially because each string branches into two choices, making it hard to track without memoization.
Recurrence:f(i, m, n) = max(f(i+1, m, n), 1 + f(i+1, m - zeros_i, n - ones_i)) if m >= zeros_i and n >= ones_i else f(i+1, m, n)
</>
Code
from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    def count_zeros_ones(s: str) -> (int, int):
        zeros = s.count('0')
        ones = len(s) - zeros
        return zeros, ones

    def dfs(i: int, zeros_left: int, ones_left: int) -> int:
        if i == len(strs):
            return 0
        zeros, ones = count_zeros_ones(strs[i])
        res = dfs(i + 1, zeros_left, ones_left)  # skip current
        if zeros <= zeros_left and ones <= ones_left:
            res = max(res, 1 + dfs(i + 1, zeros_left - zeros, ones_left - ones))
        return res

    return dfs(0, m, n)

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4
Line Notes
def count_zeros_ones(s: str) -> (int, int):Helper to count zeros and ones in a string for reuse
if i == len(strs):Base case: no more strings to consider
res = dfs(i + 1, zeros_left, ones_left)Option 1: skip current string
if zeros <= zeros_left and ones <= ones_left:Check feasibility before including current string
import java.util.*;

public class OnesAndZeroes {
    public static int findMaxForm(String[] strs, int m, int n) {
        return dfs(strs, 0, m, n);
    }

    private static int dfs(String[] strs, int i, int zerosLeft, int onesLeft) {
        if (i == strs.length) return 0;
        int zeros = 0, ones = 0;
        for (char c : strs[i].toCharArray()) {
            if (c == '0') zeros++;
            else ones++;
        }
        int res = dfs(strs, i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        return res;
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}
Line Notes
if (i == strs.length) return 0;Base case: no more strings to process
for (char c : strs[i].toCharArray())Count zeros and ones in current string
int res = dfs(strs, i + 1, zerosLeft, onesLeft);Skip current string option
if (zeros <= zerosLeft && ones <= onesLeft)Include current string if feasible
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int dfs(const vector<string>& strs, int i, int zerosLeft, int onesLeft) {
    if (i == strs.size()) return 0;
    int zeros = 0, ones = 0;
    for (char c : strs[i]) {
        if (c == '0') zeros++;
        else ones++;
    }
    int res = dfs(strs, i + 1, zerosLeft, onesLeft); // skip
    if (zeros <= zerosLeft && ones <= onesLeft) {
        res = max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));
    }
    return res;
}

int findMaxForm(vector<string>& strs, int m, int n) {
    return dfs(strs, 0, m, n);
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}
Line Notes
if (i == strs.size()) return 0;Base case: no more strings to consider
for (char c : strs[i])Count zeros and ones in current string
int res = dfs(strs, i + 1, zerosLeft, onesLeft);Option to skip current string
if (zeros <= zerosLeft && ones <= onesLeft)Include current string if possible
function findMaxForm(strs, m, n) {
    function countZerosOnes(s) {
        let zeros = 0, ones = 0;
        for (let ch of s) {
            if (ch === '0') zeros++;
            else ones++;
        }
        return [zeros, ones];
    }

    function dfs(i, zerosLeft, onesLeft) {
        if (i === strs.length) return 0;
        const [zeros, ones] = countZerosOnes(strs[i]);
        let res = dfs(i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        return res;
    }

    return dfs(0, m, n);
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4
Line Notes
function countZerosOnes(s) {Helper to count zeros and ones in a string
if (i === strs.length) return 0;Base case: no more strings to process
let res = dfs(i + 1, zerosLeft, onesLeft);Skip current string option
if (zeros <= zerosLeft && ones <= onesLeft)Include current string if feasible
⏱
Complexity
TimeO(2^n)
SpaceO(n)

Each string can be included or excluded, leading to 2^n subsets. The recursion stack depth is O(n).

💡 For n=20, this means over a million calls, which is too slow for interviews.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's nature and motivate DP.

🧠
Top-Down Memoization
💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving performance while keeping the recursive structure.

Intuition

Use a dictionary or map keyed by (index, zeros_left, ones_left) to store results of subproblems and reuse them.

Algorithm

  1. Define a recursive function with parameters index, zeros_left, ones_left.
  2. Before computing, check if result is in memo; if yes, return it.
  3. Compute by skipping or including current string if feasible.
  4. Store the result in memo and return it.
💡 Memoization reduces exponential calls to polynomial by caching repeated states.
Recurrence:f(i, m, n) = max(f(i+1, m, n), 1 + f(i+1, m - zeros_i, n - ones_i)) if m >= zeros_i and n >= ones_i else f(i+1, m, n)
</>
Code
from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    memo = {}

    def count_zeros_ones(s: str) -> (int, int):
        zeros = s.count('0')
        ones = len(s) - zeros
        return zeros, ones

    def dfs(i: int, zeros_left: int, ones_left: int) -> int:
        if i == len(strs):
            return 0
        if (i, zeros_left, ones_left) in memo:
            return memo[(i, zeros_left, ones_left)]
        zeros, ones = count_zeros_ones(strs[i])
        res = dfs(i + 1, zeros_left, ones_left)  # skip
        if zeros <= zeros_left and ones <= ones_left:
            res = max(res, 1 + dfs(i + 1, zeros_left - zeros, ones_left - ones))
        memo[(i, zeros_left, ones_left)] = res
        return res

    return dfs(0, m, n)

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4
Line Notes
memo = {}Cache to store results of subproblems
if (i, zeros_left, ones_left) in memo:Return cached result to avoid recomputation
memo[(i, zeros_left, ones_left)] = resStore computed result for future calls
res = max(res, 1 + dfs(i + 1, zeros_left - zeros, ones_left - ones))Include current string if feasible and update max
import java.util.*;

public class OnesAndZeroesMemo {
    private static Map<String, Integer> memo = new HashMap<>();

    public static int findMaxForm(String[] strs, int m, int n) {
        return dfs(strs, 0, m, n);
    }

    private static int dfs(String[] strs, int i, int zerosLeft, int onesLeft) {
        if (i == strs.length) return 0;
        String key = i + "," + zerosLeft + "," + onesLeft;
        if (memo.containsKey(key)) return memo.get(key);
        int zeros = 0, ones = 0;
        for (char c : strs[i].toCharArray()) {
            if (c == '0') zeros++;
            else ones++;
        }
        int res = dfs(strs, i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        memo.put(key, res);
        return res;
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}
Line Notes
private static Map<String, Integer> memo = new HashMap<>();Memoization cache keyed by state string
if (memo.containsKey(key)) return memo.get(key);Return cached result if available
memo.put(key, res);Store computed result for reuse
res = Math.max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));Include current string if possible
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

string makeKey(int i, int zerosLeft, int onesLeft) {
    return to_string(i) + "," + to_string(zerosLeft) + "," + to_string(onesLeft);
}

int dfs(const vector<string>& strs, int i, int zerosLeft, int onesLeft, unordered_map<string,int>& memo) {
    if (i == strs.size()) return 0;
    string key = makeKey(i, zerosLeft, onesLeft);
    if (memo.count(key)) return memo[key];
    int zeros = 0, ones = 0;
    for (char c : strs[i]) {
        if (c == '0') zeros++;
        else ones++;
    }
    int res = dfs(strs, i + 1, zerosLeft, onesLeft, memo); // skip
    if (zeros <= zerosLeft && ones <= onesLeft) {
        res = max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones, memo));
    }
    memo[key] = res;
    return res;
}

int findMaxForm(vector<string>& strs, int m, int n) {
    unordered_map<string,int> memo;
    return dfs(strs, 0, m, n, memo);
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}
Line Notes
unordered_map<string,int>& memoMemoization cache passed by reference
if (memo.count(key)) return memo[key];Return cached result if present
memo[key] = res;Store computed result for reuse
res = max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones, memo));Include current string if feasible
function findMaxForm(strs, m, n) {
    const memo = new Map();

    function countZerosOnes(s) {
        let zeros = 0, ones = 0;
        for (let ch of s) {
            if (ch === '0') zeros++;
            else ones++;
        }
        return [zeros, ones];
    }

    function dfs(i, zerosLeft, onesLeft) {
        if (i === strs.length) return 0;
        const key = i + ',' + zerosLeft + ',' + onesLeft;
        if (memo.has(key)) return memo.get(key);
        const [zeros, ones] = countZerosOnes(strs[i]);
        let res = dfs(i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        memo.set(key, res);
        return res;
    }

    return dfs(0, m, n);
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4
Line Notes
const memo = new Map();Memoization cache to store computed states
if (memo.has(key)) return memo.get(key);Return cached result if available
memo.set(key, res);Store computed result for reuse
res = Math.max(res, 1 + dfs(i + 1, zerosLeft - zeros, onesLeft - ones));Include current string if feasible
⏱
Complexity
TimeO(n * m * n)
SpaceO(n * m * n)

Memoization reduces calls to unique states bounded by number of strings and zero/one budgets.

💡 For n=600, m=100, n=100, this is feasible but still expensive.
Interview Verdict: Accepted

Memoization makes the solution efficient enough for interview constraints and is a natural step from brute force.

🧠
Bottom-Up Tabulation (2D DP Table)
💡 Tabulation builds the solution iteratively from smaller subproblems, often easier to understand and debug than recursion with memoization.

Intuition

Use a 2D dp array where dp[i][j] stores max strings with i zeros and j ones. For each string, update dp by considering inclusion.

Algorithm

  1. Initialize a 2D dp array of size (m+1) x (n+1) with zeros.
  2. For each string, count zeros and ones.
  3. Iterate zeros from m down to zeros count, and ones from n down to ones count.
  4. Update dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) to include current string.
  5. Return dp[m][n] as the answer.
💡 Backward iteration ensures each string is counted once per iteration, preserving 0/1 knapsack logic.
Recurrence:dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) if i >= zeros and j >= ones
</>
Code
from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    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], 1 + dp[i - zeros][j - ones])

    return dp[m][n]

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4
Line Notes
dp = [[0] * (n + 1) for _ in range(m + 1)]Initialize DP table with zeros for all zero/one budgets
for s in strs:Process each string to update dp
for i in range(m, zeros - 1, -1):Iterate zeros backwards to avoid reuse in same iteration
dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])Update dp with max of skipping or including current string
public class OnesAndZeroesTab {
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}
Line Notes
int[][] dp = new int[m + 1][n + 1];Create DP table for zero and one budgets
for (String s : strs)Process each string
for (int i = m; i >= zeros; i--)Iterate zeros backwards to avoid double counting
dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (const string& s : strs) {
        int zeros = 0, ones = 0;
        for (char c : s) {
            if (c == '0') zeros++;
            else ones++;
        }
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}
Line Notes
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));Initialize DP table with zeros
for (const string& s : strs)Iterate over each string
for (int i = m; i >= zeros; i--)Backward iteration to prevent reuse in same iteration
dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string
function findMaxForm(strs, m, n) {
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (const s of strs) {
        let zeros = 0, ones = 0;
        for (const ch of s) {
            if (ch === '0') zeros++;
            else ones++;
        }
        for (let i = m; i >= zeros; i--) {
            for (let j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);
            }
        }
    }

    return dp[m][n];
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4
Line Notes
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Initialize 2D DP array with zeros
for (const s of strs)Process each string
for (let i = m; i >= zeros; i--)Backward iteration to avoid double counting
dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string
⏱
Complexity
TimeO(l * m * n)
SpaceO(m * n)

For each string (l), we update a dp table of size m*n.

💡 For m=100, n=100, and l=600, this is efficient and practical.
Interview Verdict: Accepted

This is the preferred approach in interviews due to clarity and efficiency.

🧠
Space Optimized Bottom-Up (1D DP Array)
💡 We can optimize space by using a single 2D array and updating it in reverse order, reducing memory usage while preserving correctness.

Intuition

Since dp[i][j] depends only on dp[i - zeros][j - ones], we can update dp in place backwards to reuse the same array.

Algorithm

  1. Initialize a 2D dp array of size (m+1) x (n+1) with zeros.
  2. For each string, count zeros and ones.
  3. Iterate zeros from m down to zeros count, and ones from n down to ones count.
  4. Update dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) in place.
  5. Return dp[m][n] as the answer.
💡 Backward iteration prevents overwriting states needed for future calculations in the same iteration.
Recurrence:dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])
</>
Code
from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    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], 1 + dp[i - zeros][j - ones])

    return dp[m][n]

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4
Line Notes
dp = [[0] * (n + 1) for _ in range(m + 1)]Initialize DP table
for s in strs:Process each string
for i in range(m, zeros - 1, -1):Backward iteration to avoid double counting
dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])Update dp with max of skipping or including string
public class OnesAndZeroesSpaceOpt {
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}
Line Notes
int[][] dp = new int[m + 1][n + 1];Initialize DP table
for (int i = m; i >= zeros; i--)Backward iteration to prevent reuse of updated states
dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string
for (String s : strs)Process each string
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (const string& s : strs) {
        int zeros = 0, ones = 0;
        for (char c : s) {
            if (c == '0') zeros++;
            else ones++;
        }
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}
Line Notes
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));Initialize DP table
for (int i = m; i >= zeros; i--)Backward iteration to avoid double counting
dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string
for (const string& s : strs)Process each string
function findMaxForm(strs, m, n) {
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (const s of strs) {
        let zeros = 0, ones = 0;
        for (const ch of s) {
            if (ch === '0') zeros++;
            else ones++;
        }
        for (let i = m; i >= zeros; i--) {
            for (let j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);
            }
        }
    }

    return dp[m][n];
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4
Line Notes
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Initialize DP table
for (let i = m; i >= zeros; i--)Backward iteration to avoid double counting
dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string
for (const s of strs)Process each string
⏱
Complexity
TimeO(l * m * n)
SpaceO(m * n)

Same as tabulation but with optimized space usage.

💡 This approach uses less memory but same time complexity as tabulation.
Interview Verdict: Accepted

Space optimization is a nice-to-have in interviews to demonstrate deeper understanding.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, coding the bottom-up tabulation (Approach 3) is usually best for clarity and efficiency.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n)Yes (deep recursion)NoMention only - never code
2. Top-Down MemoizationO(n * m * n)O(n * m * n)Possible (deep recursion)Yes (with extra tracking)Good for explaining optimization
3. Bottom-Up TabulationO(l * m * n)O(m * n)NoYes (with parent pointers)Best to code in interview
4. Space Optimized Bottom-UpO(l * m * n)O(m * n)NoHarderMention if time permits
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice all approaches, and know when and how to present them in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem's complexity.Introduce memoization to optimize overlapping subproblems.Present the bottom-up DP solution as the optimal approach.Optionally mention space optimization if time permits.

Time Allocation

Clarify: 2min → Brute Force: 3min → Memoization: 4min → Tabulation: 5min → Testing: 3min. Total ~17min

What the Interviewer Tests

Understanding of knapsack variants, ability to optimize brute force, knowledge of DP states and transitions, and coding accuracy.

Common Follow-ups

  • What if we want to return the actual subset? → Use parent pointers or reconstruct from dp table.
  • Can this be solved with a greedy approach? → No, greedy fails due to two constraints.
💡 These follow-ups test deeper understanding and ability to extend solutions.
🔍
Pattern Recognition

When to Use

1) Problem involves selecting subsets with constraints; 2) Constraints involve two resources (zeros and ones); 3) Maximize count or value; 4) Classic knapsack structure with two dimensions.

Signature Phrases

"at most m zeros and n ones""maximum number of strings"

NOT This Pattern When

Problems with unlimited item usage or without resource constraints are different patterns.

Similar Problems

0/1 Knapsack - classic single constraint knapsackCoin Change - counting ways with constraintsTarget Sum - subset sum variant with sign constraints

Practice

(1/5)
1. You are given a set of stones with positive integer weights. You want to split them into two groups such that the difference between the sum of weights in the two groups is minimized. Which algorithmic approach guarantees finding the minimal possible difference?
easy
A. A dynamic programming approach similar to 0/1 knapsack that finds achievable sums up to half the total weight
B. A breadth-first search exploring all subsets of stones without pruning
C. A greedy algorithm that repeatedly smashes the two heaviest stones until one or none remain
D. A divide-and-conquer approach that recursively splits stones into halves and merges results

Solution

  1. Step 1: Understand the problem as partitioning stones into two subsets with minimal difference

    This is a classic subset-sum variation where we want to find a subset with sum as close as possible to half the total.
  2. Step 2: Recognize that 0/1 knapsack DP can find achievable sums up to half total weight

    By using DP to track which sums are possible, we can find the closest sum to half, minimizing the difference.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Greedy fails on some inputs; DP guarantees minimal difference [OK]
Hint: Minimal difference -> subset sum DP, not greedy [OK]
Common Mistakes:
  • Believing greedy smashing always yields minimal difference
  • Thinking divide-and-conquer without DP suffices
  • Assuming BFS is efficient enough here
2. Consider the following Python function implementing the DP with bitmask tabulation approach for partitioning an array into k equal sum subsets. What is the return value when called with nums = [1, 2, 3, 4] and k = 2?
from typing import List

def canPartitionKSubsets(nums: List[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                if dp[next_mask] == -1:
                    dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0
easy
A. True
B. False
C. Raises an exception due to index error
D. Returns None

Solution

  1. Step 1: Calculate total and target

    Sum is 10, k=2, target subset sum = 5.
  2. Step 2: Trace dp updates

    DP explores subsets; for example, {1,4} and {2,3} both sum to 5, so dp[(1<<4)-1] = 0, returning True.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Partition exists: [1,4] and [2,3] [OK]
Hint: Sum divisible by k and dp final state 0 means partition possible [OK]
Common Mistakes:
  • Confusing dp array indexing or bitmask operations
  • Forgetting to check if largest element exceeds target
3. Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?
easy
A. 1
B. 3
C. 0
D. 2

Solution

  1. Step 1: Trace initial dp array

    total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)
  2. Step 2: Process num=1 and num=2 updating dp

    After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Two ways: +1-2 and -1+2 sum to 1 [OK]
Hint: Offset indexing maps sums to dp indices [OK]
Common Mistakes:
  • Off-by-one errors in indexing dp array
4. Suppose the problem is modified so that each number in the input array can be used multiple times to form the subsets. Which change to the DP approach correctly solves this variant?
hard
A. Keep the same code but iterate the dp array backwards to avoid reuse of elements
B. Change the inner loop to iterate forwards from num to target to allow multiple uses of the same element
C. Use recursion without memoization to explore all combinations with repeats
D. Double the dp array size to track counts of each element used

Solution

  1. Step 1: Understand the difference between 0/1 and unbounded knapsack

    Allowing multiple uses means the problem becomes unbounded knapsack, which requires forward iteration over dp array.
  2. Step 2: Identify correct dp iteration direction

    Iterating forwards from num to target allows dp[w] to build upon dp[w - num] updated in the same iteration, enabling multiple uses.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Backward iteration prevents multiple uses; forward iteration enables them [OK]
Hint: Forward dp iteration enables multiple uses of elements [OK]
Common Mistakes:
  • Using backward iteration from 0/1 knapsack
  • Ignoring iteration direction for repeats
5. Suppose the problem is modified so that jobs can be scheduled multiple times (i.e., unlimited reuse of the same job), still without overlapping. Which modification to the optimal DP approach is correct?
hard
A. Replace binary search with linear search to find compatible jobs and keep DP unchanged
B. Use a 1D DP array indexed by time and for each time, consider all jobs that can start then, allowing reuse
C. Keep the same DP with binary search but remove the skip option to always take the current job
D. Sort jobs by start time and use memoized recursion without binary search

Solution

  1. Step 1: Understand unlimited reuse impact

    Allowing multiple uses of the same job means the problem resembles unbounded interval scheduling with no overlaps.
  2. Step 2: Modify DP approach

    Use a 1D DP array indexed by time (e.g., dp[t] = max profit up to time t). For each time, consider all jobs starting at or after t, allowing reuse by updating dp[end_i] = max(dp[end_i], dp[start_i] + profit_i).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search and skip logic do not handle reuse; time-indexed DP handles multiple scheduling [OK]
Hint: Use time-indexed DP for unlimited job reuse [OK]
Common Mistakes:
  • Trying to reuse binary search DP without changes
  • Removing skip option breaks correctness
  • Sorting by start time only
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard