Coding Interview Patterns Module 8 – Stacks and monotonic stacks
Greedy choices with a monotonic stack
Delete k digits to leave the smallest number, and build the smallest code with each letter once, by taking back earlier choices with a monotonic stack.
What you will learn
- Delete k digits of a number to leave the smallest possible number in O(n)
- Prove that taking back a larger digit before a smaller one is safe
- Handle leftover deletions, leading zeros and a result with no digits left
- Build the smallest subsequence that uses each distinct letter exactly once
- Test a greedy stack against an exhaustive search on short random inputs
Before you start
What you’ll learn · Before you start
What you will learn
- Delete k digits of a number to leave the smallest possible number in O(n)
- Prove that taking back a larger digit before a smaller one is safe
- Handle leftover deletions, leading zeros and a result with no digits left
- Build the smallest subsequence that uses each distinct letter exactly once
- Test a greedy stack against an exhaustive search on short random inputs
Before you start
On this page
Some greedy problems build an answer from left to right and take back earlier choices: to delete two digits of 4253 and leave the smallest number, the 2 takes back the 4 and the 3 takes back the 5, which leaves 23. When a better item arrives, they undo the items before it that it beats, as far as a budget allows. A monotonic stack: A stack whose values stay in order from bottom to top, because each new item first pops every item it settles. It finds the nearest earlier or later larger, or smaller, item for every item in one pass. More in “Stack patterns: nesting and undo” holds the choices made so far, and its pops are the take-backs. The best-known case is deleting k digits from a number to leave it as small as possible: a digit followed by a smaller one should usually go, because the first place where two candidates differ decides which is smaller. One pass gives the answer in O(n), where trying every set of deletions grows exponentially. The same idea builds the smallest subsequence: Items taken from a sequence in their original order but not necessarily side by side: 1, 3, 4 is a subsequence of 1, 2, 3, 4. A substring or a subarray must be contiguous. More in “Which pattern? A decision guide” that uses each distinct letter exactly once. That makes a short code for a name: each letter once, in the name’s order, first in alphabetical order.
The problem: the smallest reference number
The problem
A receipt printer prints a code of n digits. To make a short reference number, exactly k of its digits are deleted
and the others are kept in their order. Return the smallest number that can be left, written without leading
zeros, or "0" when no digit, or only zeros, are left. Limits: 1 ≤ k ≤ n ≤ 100,000; the code is a string of n
digits, and it may contain zeros anywhere.
Four examples, which every program in this lesson runs:
"4253"with k = 2 gives"23"."30420"with k = 1 gives"420": deleting the 3 leaves0420."12345"with k = 2 gives"123"."9"with k = 1 gives"0": nothing is left.
The digits kept stay in order; leading zeros do not count
Text description of the diagram
The figure shows the first two examples of the problem as rows of digit boxes. Deleted digits have dashed borders and kept digits solid ones.
- The code 4253 with k = 2: the 4 and the 5 are deleted, and the 2 and the 3 are kept, in their order, which leaves 23. No other choice of two digits leaves a smaller number: 25, 43, 45, 53 and 42 are all larger.
- The code 30420 with k = 1: the 3 is deleted and 0420 is kept. Read as a number it is 420, because the leading 0 is dropped.
In both rows, each deleted digit is larger than the digit right after it.
The brute force: try every set of deletions
Every candidate keeps n − k digits, so candidates of the same code can be compared as text, character by character: their lexicographic order: The order a dictionary uses: two sequences are compared at the first place where they differ, and the one with the smaller item there comes first. Numbers with the same number of digits compare this way as text. is their order as numbers. The brute force tries every set of positions to keep and returns the smallest:
"""The smallest number left after deleting k digits, the brute force: try every set of k digits to delete."""
from itertools import combinations
from math import comb, lgamma, log
def smallest_after_removals_brute(code, k):
"""The smallest number (as text, without leading zeros) left after deleting exactly k digits of code."""
best = None
tried = 0
for kept in combinations(range(len(code)), len(code) - k): # the positions that stay, in order
candidate = "".join(code[i] for i in kept) # every candidate has n - k digits, so text order is number order
tried += 1
if best is None or candidate < best:
best = candidate
return best.lstrip("0") or "0", tried
print(smallest_after_removals_brute("4253", 2)[0])
print(smallest_after_removals_brute("30420", 1)[0])
print(smallest_after_removals_brute("12345", 2)[0])
print(smallest_after_removals_brute("9", 1)[0])
answer, tried = smallest_after_removals_brute("7051938204618372", 8)
print(f"16 digits, delete 8: {answer} after {tried:,} candidates")
for n in (20, 30, 40):
print(f"{n} digits, delete {n // 2}: {comb(n, n // 2):,} candidates")
digits = int((lgamma(100_001) - 2 * lgamma(50_001)) / log(10)) + 1
print(f"100,000 digits, delete 50,000: a count of candidates with {digits:,} digits")Output
23 420 123 0 16 digits, delete 8: 418372 after 12,870 candidates 20 digits, delete 10: 184,756 candidates 30 digits, delete 15: 155,117,520 candidates 40 digits, delete 20: 137,846,528,820 candidates 100,000 digits, delete 50,000: a count of candidates with 30,101 digits
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 removals_brute.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
It is correct and quick for 16 digits, 12,870 candidates. The count is the binomial coefficient C(n, k), which is largest when k is half of n: 155 million candidates for 30 digits, 138 billion for 40, and for the limit of 100,000 digits a number that itself has 30,101 digits. No time limit allows that.
Checkpoint
Check: What trying every set of deletions costs
What to notice
All candidates have the same length, so the leftmost digit where two of them differ decides which is smaller, and the leftmost digits matter most. A digit followed by a smaller one is a poor choice for its place: deleting it moves the smaller digit one place to the left, and nothing later makes up for a larger digit further left. So keep digits from left to right, and take back an earlier digit when a smaller one arrives, while deletions remain. Taking back the most recent choice first is the stack cue of this module.
Checkpoint
Check: Why the leftmost digits matter most
The questions below practise both ideas.
Practice that adapts to you
Practise this lesson
6 questions about 7 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
A stack takes back larger digits while deletions last Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- A dry run on 4253 with k = 2
- Why taking back a larger digit is safe: the proof
- The code in 14 languages, each with its own stack of characters
- Slips, edge cases and a stress test
- The smallest code that uses each letter once
- Practise: the smallest department code
- Build the smallest code that uses each letter once
- Variants and follow-up questions, answered
- Interview questions
- Explain why deleting a digit that is larger than the digit after it never makes the result worse, and turn that into a proof that the stack method returns the smallest number.
- Your remove-k-digits solution passes the examples but fails hidden tests. List the edge cases you would test, the bug each one catches, and the smallest input for each.
- A code of 10⁹ digits arrives as a stream, and exactly 10⁶ of its digits must be deleted to leave the smallest number, which you write out as you go. How much memory do you need, and when can a digit be written?
- Key takeaways
2 diagrams · 3 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 35 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- lexicographic order
- The order a dictionary uses: two sequences are compared at the first place where they differ, and the one with the smaller item there comes first. Numbers with the same number of digits compare this way as text.
References
- Built-in types: str.lstrip() (Python Software Foundation)
- itertools.combinations() (Python Software Foundation)
- math.comb() (Python Software Foundation)
- Array: length (setting it shortens the array) (MDN Web Docs (Mozilla))
- Java SE 25 API: StringBuilder (setLength) (Oracle)
- std::basic_string::find_first_not_of (cppreference.com)
- Go standard library: strings.TrimLeft (The Go Authors)
- StringBuilder.Length (setting a smaller length truncates) (Microsoft)
- Kotlin standard library: StringBuilder.setLength (JetBrains)
- Dart API: List.length (setting it changes the number of elements) (Dart (Google))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress