Greedy removal with a stack

45 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You have the number 1432219 and must delete exactly 3 digits so that what is left is as small as possible. The digits keep their order; you cannot shuffle them.

By hand you could try every choice of 3 digits to delete. There are 35 ways to pick 3 positions out of 7, and for each you would read a 4-digit number and compare. For a number with 100 digits and 10 deletions there are about 17 trillion ways. Trying them all is hopeless.

Think about what makes a number small. The leftmost digit matters most: 1xxx is smaller than any 2xxx. So the first thing you want is the smallest possible leading digit, then the smallest possible second digit, and so on. In 1432219 the first digit 1 is already the smallest it could be. The second digit is 4, and right after it comes 3, which is smaller. Deleting the 4 makes the second digit 3. That is the whole idea: a digit is worth deleting when the digit after it is smaller.

Build the structure, one piece at a time

Piece 1: a pile of kept digits. A stack is a pile you add to and remove from only at the top. We walk the digits left to right and push each one onto the pile of digits we are keeping.

Piece 2: the removal rule. Before pushing a new digit, look at the top of the pile. If the top digit is bigger than the new digit and we still have deletions left, pop it (that is one deletion). Repeat while the top is still bigger. Then push the new digit.

Piece 3: leftovers. If deletions remain after the last digit, remove them from the top of the pile, because the top holds the largest digits of an increasing run. Finally strip leading zeros.

Follow the example with k = 3:

The pile reads 1219, which is the answer. Notice the pile tends to be non-decreasing from bottom to top; it stops being perfectly sorted only when the deletions run out.

Why it is correct

The invariant: after processing the first i digits with some deletions spent, the pile is the smallest string you can get from those i digits using that many deletions.

The argument is an exchange. Suppose the top of the pile is a, the new digit is b, and a > b. Any final answer that keeps a and b both has a before b. Compare it with the answer that deletes a instead of some later digit: the two strings agree up to the position of a, and there one has a while the other has b or something that came after. Since a > b, the second string is smaller. So deleting the bigger earlier digit never hurts, and the greedy pop is safe. When a ≤ b, deleting a would put b or something larger in its place, which cannot be smaller, so keeping a is right.

If deletions are left at the end, the pile is non-decreasing (no pop was ever refused for lack of deletions, or they would be used up), so the biggest digits are at the top and removing them is the best use.

Why it is fast

Every digit is pushed once and popped at most once. The while loop only runs while it pops, so its total work is bounded by the number of pops.

pushes + pops ≤ 2n, so the time is O(n) for n digits

Compare with trying every subset: 17 trillion checks for 100 digits versus 200 pile moves.

How to recognise it in an interview

Look for "remove k digits (or characters) to get the smallest (or largest) result", "most competitive subsequence of length k", "smallest subsequence containing each letter once". The order must be preserved and the goal is lexicographic. Say: "Walk left to right keeping a stack; whenever the top is worse than the newcomer and I can still delete, pop it."

Remove K Digits is the example above. Find the Most Competitive Subsequence is the same with k = n − (wanted length). Remove Duplicate Letters adds two checks before popping: the top letter must appear again later, and the new letter must not already be in the pile.

02The idea in one line

Pop a bigger previous digit while you still have removals left.

Reach for it when: Remove k digits, smallest subsequence, competitive subsequence, remove duplicate letters.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Remove K Digits on '1432219', k=3. These are its captions in order, so you can follow without the video or check a step you missed.

1. Pop a bigger previous digit while removals remain
2. Digit 1
3. Keep 1
4. Digit 4
5. Keep 4
6. Digit 3
7. 4 > 3: remove 4, k = 2
8. Keep 3
9. Digit 2
10. 3 > 2: remove 3, k = 1
11. Keep 2
12. Digit 2
13. Keep 2
14. Digit 1
15. 2 > 1: remove 2, k = 0
16. Keep 1
17. Digit 9
18. Keep 9
19. Kept digits read 1219: the smallest number
20. Each digit pushed once, popped at most once: O(n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Monotonic Stack: Next greater element, Largest rectangle (bounds by pops), Previous and next smaller (both sides).