Monotonic Stack — Remove K Digits
↗ LeetCode: Remove K Digits · Medium · pattern chapter →
Given a numeric string num (no leading zeros unless it's "0") and integer k, remove k digits to yield the smallest possible number. Return as a string; strip leading zeros.
Example 1 — num = "1432219", k = 3 → "1219"Example 2 — num = "10200", k = 1 → "200" (strip leading zero) Example 3 — num = "10", k = 2 → "0"
Constraints — 1 ≤ k ≤ n ≤ 10⁵. Brute tries every combination of k removals — O(C(n,k)) explodes past k=10 (C(10⁵,50) ≈ 10²⁰⁰, ~10¹⁹¹ year dies). Monotonic stack pops digits greedily → O(n) = 10⁵ ops (~10⁶ pushes counting stack churn) = <5 min under 10× throughput.
Interview timer00:00
Approach 1 — Try every subset of digits to remove
O(C(n, k)) — exponential. Baseline.
Approach 2 — Monotonic increasing stack (canonical greedy)
Insight. Building the result left-to-right, whenever the next digit is smaller than the top of the stack, popping the top strictly improves the number (a smaller digit in a higher position dominates). Keep popping while we still have budget k > 0.
End case. If k > 0 after the loop (input was monotonically non-decreasing), pop k off the end.
Trap — strip leading zeros at the end, but preserve at least one digit ("0").
String removeKdigits(String num, int k) {
Deque<Character> st = new ArrayDeque<>();
for (char c : num.toCharArray()) {
while (!st.isEmpty() && k > 0 && st.peek() > c) { st.pop(); k--; }
st.push(c);
}
while (k-- > 0 && !st.isEmpty()) st.pop();
StringBuilder sb = new StringBuilder();
while (!st.isEmpty()) sb.append(st.pollLast());
int i = 0;
while (i < sb.length() - 1 && sb.charAt(i) == '0') i++;
return sb.substring(i);
}Wait — should be 1,2,1,9? Let me reconsider: after i=5 (digit 1), we pushed 1 but couldn't pop because k=0 already. So stack = 1,2,2,1. Then i=6 pushes 9 → 1,2,2,1,9. But we've popped 3 in total. Original 7 digits, removed 3, keep 4. Result "1219" — actually 1,2,1,9 which means one of the 2s was popped. Let me re-examine trace notes. Actually looking at k count — pops so far: 4, 3, 2 = 3 pops. Result stack after full sweep: 1, 2, 2, 1, 9 (5 elements from 7, but that's only 2 popped). One more implicit pop when we shrink — hmm.
Actually the correct trace: pop when strictly smaller. On digit 2 (i=3), we pop 3 → k=2. On digit 2 (i=4), stack top is 2 == 2 → no pop. On digit 1 (i=5), stack top is 2 → pop k=1, then top is 2 again → pop k=0. Stack now 1, 1. Push 1 → 1, 1, 1. Push 9 → 1, 1, 1, 9. So result = 1119? But LC answer is 1219.
Actually LC says "1432219", k=3, answer "1219". Let me retrace by hand: 1 4 3 2 2 1 9. Greedy scan:
- 1 → stack [1]
- 4 → 4 > 1, push. stack [1, 4]
- 3 → 3 < 4, pop k=2. stack [1]; 3 > 1, push. [1, 3]
- 2 → 2 < 3, pop k=1. [1]; 2 > 1, push. [1, 2]
- 2 → 2 == 2, push. [1, 2, 2]
- 1 → 1 < 2, pop k=0. [1, 2]; k exhausted, push 1. [1, 2, 2, 1]
- 9 → push. [1, 2, 2, 1, 9]
Result: 12219 (5 digits — but we had 7, removed 3 → should have 4). Hmm. Let me recount pops: 4, 3, 2 = 3 pops. So 7−3=4 remain. Stack has 5, but one push happened after k was 0. Let me recount: pushes 1,4,3,2,2,1,9 = 7 pushes. Pops: 4 (i=1→2), 3 (i=2→3), 2 (i=3→4) = 3 pops (k=3). So stack = 7-3 = 4 remain: 1, 2, 1, 9. Result = 1219. ✓
So the correct trace at i=5 (digit 1): after previous [1, 2, 2], seeing 1: pop 2 (top) with k=1→0. Push 1. Stack = [1, 2, 1]. Then i=6 push 9 = [1, 2, 1, 9]. My earlier trace had an error. Let me fix.
Complexity — Time O(n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Enumerate subsets | O(C(n,k)) | O(k) | baseline |
| Monotonic stack | O(n) | O(n) | canonical |
When to use which
- "Smallest / largest number after removing k digits" → monotonic stack with correct order.
- "Largest number" → decreasing stack; pop when top < next.
- "Remove exactly k characters to make lex smallest string" → same greedy.
- "Keep at most k digits" → cap stack size to k.
Related problems
- Largest Rectangle in Histogram — pop-when-shrinking stack
- Remove Duplicate Letters — same greedy with counts
- Create Maximum Number — two-array variant