Ones and Zeroes

Ones and Zeroes

What is this problem about?

The Ones and Zeroes problem gives you a list of binary strings and two limits m (max zeros) and n (max ones). Find the maximum number of strings you can include such that the total zeros ≤ m and total ones ≤ n. This coding problem is a 2D variant of the 0/1 knapsack problem. The array, string, and dynamic programming interview pattern is the core.

Why is this asked in interviews?

Uber, Meta, Google, and Bloomberg ask this because it extends 0/1 knapsack to two resource dimensions (zeros and ones). The ability to generalize knapsack DP to multiple constraints is tested. Each string is an "item" with two "weights" (zeros count and ones count) and "value" 1.

Algorithmic pattern used

2D 0/1 knapsack DP. dp[i][j] = maximum strings using exactly i zeros and j ones. For each string with z zeros and o ones: update DP in reverse: dp[i][j] = max(dp[i][j], dp[i-z][j-o]+1) for i from m down to z, j from n down to o.

Example explanation

strs=["10","0001","111001","1","0"], m=5, n=3.

• "10": z=1, o=1. Process in reverse order.
• "0001": z=3, o=1. dp updated.
• "111001": z=2, o=4. dp updated.
• "1": z=0, o=1. dp updated.
• "0": z=1, o=0. dp updated. Maximum strings within (5,3): dp[5][3] = 4 ("10","0001","1","0").

Common mistakes candidates make

• Updating DP in forward order (allows same string to be counted multiple times — 0/1 knapsack must go backwards).
• Using 1D instead of 2D DP.
• Counting zeros and ones incorrectly.
• Off-by-one in the DP reverse loop bounds.

Interview preparation tip

2D knapsack problems always use reverse DP iteration to enforce the "at most once" constraint. The pattern: outer loop over items, inner two loops from max capacity down to item's weight. Practice 1D knapsack first, then generalize to 2D — the structure is identical with an extra dimension. This technique applies to "select items under two resource limits" in scheduling, resource allocation, and budget problems.