Counting & Bound Arguments

Some greedy problems don't need you to build the answer step by step at all. A short counting argument shows the answer must be at most some bound, and a simple construction shows the bound is reachable. Others need only a tiny summary of the state, like a range of possible counts, instead of exploring every choice. Both turn an exponential search or a heap simulation into a formula or a single pass.

The idea#

The pattern comes down to two moves.

Bound, then reach it. Find the one quantity that limits the answer (the largest pile, the most frequent task, the most significant bit). Show the answer can't beat a bound based on it, then show a greedy order achieves that bound.
Summarize the choices. When a wildcard gives several options, you often don't need each branch, only the range of outcomes. If every value in the range is reachable, tracking [lo, hi] is enough.

How to spot it#

These signals in a question point to a counting or bound argument.

"Can't do the same thing twice in a row", "no two adjacent equal": the most frequent item is the bottleneck.
Wildcards (* can be (, ) or empty) where a DP over every choice feels heavy.
Binary values where the leftmost bit outweighs everything after it.
A heap or step-by-step simulation that works but is slower than the problem suggests.

Template#

The first move needs no loop at all. Find the bottleneck, compare it with everything else, and pick the case.

bottleneck = the quantity that limits the answer   # largest, most frequent
rest = everything else combined
if rest can separate or absorb the bottleneck:
    return the full total                           # the bound is reachable
else:
    return the most the rest can support            # some items are stranded

The second move tracks a range instead of every branch. When a wildcard can raise, lower or keep a count, carry its lowest and highest possible value.

lo = hi = starting count
for each symbol:
    lo += the smallest change the symbol can cause
    hi += the largest change the symbol can cause  # differ for a wildcard
    if hi falls below the valid floor: fail     # no choice can fix it
    clamp lo to the valid floor                 # lower values were never valid
succeed if the target value lies in [lo, hi]

Both replace a search or a simulation with $O(n)$ work, or $O(1)$ after a sum.

Pitfalls#

These mistakes cause the most wrong answers.

Getting the two cases of a bound backwards. Check which side of the bound strands items, and test the boundary value itself.
Forgetting to clamp the low end of a range. A low end below the floor means "use fewer wildcards that way", not "invalid".
Exiting early on the wrong end. Only the high end falling below the floor proves failure; the low end can recover.
Doing dependent greedy steps in the wrong order. When one fix decides the next (rows before columns, say), do the dominant one first.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Maximum Number of Weeks for Which You Can Work

A max-heap simulation works, but a bound is shorter. Let largest be the biggest project and rest the sum of the others. If largest <= rest + 1, the others can separate every milestone, so the answer is the total. Otherwise each other milestone separates two of the largest: 2 * rest + 1.

Hint: Valid Parenthesis String

A memo over (index, open_count) with three branches per star works. Instead, keep lo and hi, the fewest and most unclosed (. A * moves lo down and hi up. Fail if hi < 0, clamp lo at 0, and the string is valid if lo == 0 at the end.

Hint: Score After Flipping Matrix

The leftmost bit is worth more than all later bits combined ( $2^{n-1} > 2^{n-1} - 1$ ). So first flip every row that starts with 0. Then flip each remaining column if it has more 0s than 1s.

Hint: Lemonade Change

Keep counts of $5 and $10 bills. For a $20, give a $10 and a $5 if you can, and three $5s only otherwise: a $5 can make change for anything and a $10 can't. If the $5 count drops below zero, fail.

Hint: Minimum Deletions to Make Character Frequencies Unique

Process the frequencies. While a frequency is already taken, lower it by one and count a deletion, until it is free or zero.

Hint: Reorganize String

The bound works like Maximum Number of Weeks. It is possible only if the most frequent character appears at most (n + 1) // 2 times.

Hint: Merge Triplets to Form Target Triplet

Throw away every triplet with a value larger than the target in any position; using it would overshoot forever. The answer is yes if the remaining triplets, together, hit each target value in some position.

Key takeaways#

Find the bottleneck quantity and bound the answer with it.
A bound plus a construction that meets it is a full proof.
When choices only shift a count, track its [lo, hi] range instead of every branch.
A heap simulation that works is a hint that a formula might exist.

Core idea#

Replace a simulation with a count or a bound. Show the answer cannot beat a bound, then show a greedy order reaches it. When choices only shift a count, track the [lo, hi] range.

Key points#

Find the bottleneck: the largest pile, the most frequent item, the top bit.
A bound plus a construction that meets it is a full proof.
Maximum Number of Weeks: if largest <= rest + 1, the answer is total. Otherwise it is 2 * rest + 1.
Reorganize String is possible only if the top count is at most (n + 1) // 2.
Score After Flipping Matrix: the top bit outweighs all later bits. Flip rows that start with 0, then flip columns with more 0s than 1s.
Lemonade Change: for a $20, give a $10 and a $5 before three $5s.
Merge Triplets: drop triplets that exceed the target anywhere, then check coverage.
A heap simulation that works hints that a formula exists.

Template#

lo = hi = 0                         # min and max open count
for each ch in s:
    if ch opens: lo += 1, hi += 1
    if ch closes: lo -= 1, hi -= 1
    if ch is a wildcard: lo -= 1, hi += 1   # close, open or empty
    if hi < 0: fail                 # no choice can fix it
    lo = max(lo, 0)
succeed if lo == 0

Pitfalls#

Reversing the two cases of a bound. The stranded case is largest > rest + 1.
Forgetting to clamp lo at 0 in Valid Parenthesis String.
Exiting on lo < 0. Only hi < 0 proves the string cannot be fixed.
Flipping columns before fixing the rows' first bits.

Say it in an interview#

"The largest pile is the bottleneck. If the rest can separate it, every item fits."
"A star only shifts the open count, so tracking its range replaces every branch."