Monotonic Stack for Greedy Choices

Some problems ask you to build the smallest (or largest) sequence by keeping or removing items, where each decision is made against the latest item you kept. A monotonic stack fits well here: the stack is the answer under construction, and a new item can evict worse items from its top. A hint that the answer should come out in ascending or descending order is another strong cue.

The idea#

Removing digits to get the smallest number shows why this greedy choice is safe. Compare two numbers with the same length digit by digit: the first position where they differ decides. So a smaller digit earlier always beats a bigger digit earlier, whatever follows. When the current digit is smaller than the stack's top and you still have removals left, popping the top can only make the result smaller.

The same "is the top still useful?" question also works when you aren't building an ordered result. In a pattern search, such as the 132 pattern below, a new value can make the top useless as a candidate, so you pop it. The stack then holds only candidates that could still matter.

How to spot it#

The decision for each item depends on the latest kept items. Look for these signals.

"Remove k digits / characters to make the smallest (or largest) result".
"Lexicographically smallest" string built by pushing to and popping from a buffer.
"Does a pattern like i < j < k with nums[i] < nums[k] < nums[j] exist?"
You traverse the input and each item's fate is decided against what you kept so far.

Template#

The stack is the result so far. A better item evicts worse tops while the budget allows.

stack = empty
for each item in input:
    while budget left and stack and top is worse than item:
        pop top                     # item earlier beats top earlier
        spend one unit of budget
    push item
if budget left:
    remove the leftover from the end   # the tail is the worst part
clean up and return stack as the result

Each item is pushed and popped at most once, so the scan is $O(n)$ .

To see the template on the digit example, here is the trace for the smallest number after removing k = 3 digits from 1432219. "Worse" means a bigger digit.

Digit	Pops (`k` left)	Stack after
1		`1`
4		`14`
3	4 (2)	`13`
2	3 (1)	`12`
2		`122`
1	2 (0)	`121`
9		`1219`

Pitfalls#

These slips leave the result too big or plain wrong.

Forgetting leftover removals. If the input is already in order (like "12345"), nothing pops. The remaining budget must come off the end, where the worst items are.
Leading zeros. A numeric result may start with zeros after the pops. Strip them, and return "0" if nothing is left.
Popping without a budget. Each pop spends one removal; check the budget in the while condition.
Comparing with the top only once. Use a while, not an if. The useful candidate can sit below a useless top.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

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

Hint: Remove K Digits

Keep a stack of digits that never decreases from bottom to top. Pop while k and the top is bigger than the new digit. Trim any leftover k from the end, then strip leading zeros and return "0" if nothing is left.

Hint: Using a Robot to Print the Lexicographically Smallest String

Send the top of t to paper when it's no larger than every character still left in s: nothing later could beat it. Precompute the suffix minimum of s, with a sentinel past the end that sorts after z (such as "{"). After each push, pop to paper while top <= suffix_min[i + 1].

Hint: 132 Pattern

Push each value as (value, min_before_it): the value is a candidate j, and the stored minimum is the best i for it. For each new num (a candidate k), pop every top whose value is <= num. If the stack is still non-empty and the top's stored minimum is < num, you found the pattern. Then push (num, running_min).

Hint: 132 Pattern: why popping is safe

If num >= j, any future k that fits under j also fits under num. The stored minimum for num is no larger than the one for j. So num is at least as good a candidate, and j can go.

Key takeaways#

A smaller item earlier always wins, so evict bigger tops while you're allowed.
The stack is the answer under construction; its order is the order you want.
Leftover removals come off the end.
Store extra context in each entry (like the minimum before it) to test patterns in one pass.
The core question every time: is the top still useful?

Core idea#

The stack is the answer under construction. A new item evicts worse items from the top while that can only improve the result.

Key points#

A smaller digit earlier always beats a bigger digit earlier, whatever follows.
In Remove K Digits, each pop spends one of the k removals.
Leftover removals come off the end, where the largest digits are.
The core question every time: is the top still useful?
Spot it: "remove k digits for the smallest result", "lexicographically smallest", the pattern i < j < k with nums[i] < nums[k] < nums[j].

Variants#

Robot printing: precompute the suffix minimum of s with a sentinel "{". Pop to paper while top <= suffix_min[i + 1].
132 Pattern: push (value, min_before_it). For each num, pop tops with value <= num. If the new top's stored minimum is < num, return True. Then push (num, running_min).
Popping in the 132 pattern is safe. If num >= j, num is at least as good a candidate as j.

Template#

stack = empty
for each item in input:
    while budget left and stack and top is worse than item:
        pop top                    # item earlier beats top earlier
        spend one unit of budget
    push item
if budget left: remove the leftover from the end
clean up (e.g. strip leading zeros) and return stack

Pitfalls#

Forgetting leftover removals. "12345" pops nothing, so trim k from the end.
Leading zeros. Strip them, and return "0" if nothing is left.
Popping without a budget. Check k in the while condition.
Comparing with the top only once in the 132 pattern. The right j can sit below a useless top.

Say it in an interview#

"A smaller digit earlier always wins, so pop bigger tops while removals remain."
"Each entry carries the minimum before it, so one pass tests the 132 pattern."