What is the brute force approach and complexity for Ones and Zeroes?

Recurse on every string: skip it, or take it when both budgets can pay for it with time complexity O(2^L) and space complexity O(L).

What is the optimal approach and complexity for Ones and Zeroes?

Keep one dp[z][o] table; for each string, both loops go from the budget down to the string's counts with optimal time complexity O(L · m · n) and space complexity O(m · n).

How do you identify the pattern for Ones and Zeroes?

Look for key signals in the prompt: "at most m zeros and at most n ones" indicates Two capacities at the same time, so the state is (zeros used, ones used) → a 2-D table.; "each string can be picked at most once" indicates Each string is in or out, so both capacity loops must go high → low.; "the largest number of strings" indicates Each pick is worth 1, so each cell stores a count and takes the max of skip and take + 1..

Ones and Zeroes

Medium·LeetCode #474 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given a list of binary strings strs. Each string is made only of the digits 0 and 1. You are also given two budgets: m is the most zeros you may use in total, and n is the most ones you may use in total.

Pick as many strings as you can, so that the strings you pick use at most m zeros and at most n ones together. Each string can be picked at most once.

Return the largest number of strings you can pick. The function is int findMaxForm(vector<string>& strs, int m, int n).

Input

strs, a list of strings made only of 0 and 1. m, the zero budget. n, the one budget.

Output

A single number: the largest count of strings you can pick while staying within both budgets.

Example 1

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

Output: 4

Pick "10", "0001", "1" and "0". They use 1 + 3 + 0 + 1 = 5 zeros and 1 + 1 + 1 + 0 = 3 ones. "111001" alone has four 1s, which is over the budget.

Example 2

Input: strs = ["10", "0", "1"], m = 1, n = 1

Output: 2

"0" and "1" together use one zero and one one. "10" also uses one of each, so picking it blocks both of them.

Example 3

Input: strs = ["00", "011", "101"], m = 2, n = 4

Output: 2

"00" uses both zeros, so nothing else fits after it. "011" and "101" together use 2 zeros and 4 ones, which fits, so the answer is 2.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“at most m zeros and at most n ones”

→ Two capacities at the same time, so the state is (zeros used, ones used) → a 2-D table.

“each string can be picked at most once”

→ Each string is in or out, so both capacity loops must go high → low.

“the largest number of strings”

→ Each pick is worth 1, so each cell stores a count and takes the max of skip and take + 1.

Approach Complexity Ladder

Brute Force — skip or take each stringO(2^L)O(L)

Recurse on every string: skip it, or take it when both budgets can pay for it

Better — 3-D table over strings, zeros and onesO(L · m · n)O(L · m · n)

Store dp[i][z][o] for every prefix of strings and every budget pair

Optimal — one 2-D table, both budgets high → lowO(L · m · n)O(m · n)

Keep one dp[z][o] table; for each string, both loops go from the budget down to the string's counts

Brute Force Intuition

Go through the strings in order. Each one is either skipped, or taken when both budgets can pay for it. The answer is the bigger count of the two choices. Every subset of strings gets tried, so the same budget state is reached again and again.

Recognition rule for this sub-pattern:

Each item once. dp[c] = max(dp[c], dp[c − w] + v), capacity loop goes high → low.

Remember this · DP — Knapsack

Trigger

Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.

Think

Is this "choose some items so their total is X"?

Key question

Can each item be used once (loop capacity backwards) or many times (loop forwards)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture