Remove K Digits
Remove k digits to make the smallest number with a greedy monotonic stack: drop a digit whenever a smaller one comes after it.
Problem Understanding
Remove K Digits: given a non-negative integer as a string num and an integer k, remove exactly k digits so the remaining number is as small as possible. Return it without leading zeros, or "0".
Example: num = "1432219", k = 3 returns "1219": removing 4, 3 and 2 does it.
The Intuition: Small Digits Belong on the Left
The leftmost digit matters most. Whenever a digit is followed by a smaller one, removing it improves the number at that position, so do it greedily. A stack makes this one pass, and it stays non-decreasing, like every monotonic stack:
- For each digit
d, while removals remain and the top is bigger thand, pop the top (one removal). - Push
d. - If removals are left, the digits never fall, so drop them from the end.
- Strip leading zeros; an empty result is
"0".
The pop rule is the same "top loses to the newcomer" loop as Next Greater Element I, with a budget of k pops.
Interactive Walkthrough
The digits of num are on top; below them, the digits kept on the stack. A removed digit turns red for one step. Try Example 2 for the leading-zero case and Rising for removals taken off the end.
Dry Run Table
Input: num = "1432219", k = 3
| Digit | Removed | k left | Stack after |
|---|---|---|---|
| 1 | — | 3 | 1 |
| 4 | — | 3 | 14 |
| 3 | 4 | 2 | 13 |
| 2 | 3 | 1 | 12 |
| 2 | — | 1 | 122 |
| 1 | 2 | 0 | 121 |
| 9 | — | 0 | 1219 |
Answer: "1219".
The Solution Template
A stack of kept digits, popped while removals remain and the top is bigger.
Remove K Digits Code
1var removeKdigits = function(num, k) {2 const stack = [];3 for (const d of num) {4 while (k && stack.length && stack[stack.length - 1] > d) {5 stack.pop();6 k--;7 }8 stack.push(d);9 }10 stack.length -= k;11 return stack.join('').replace(/^0+/, '') || '0';12};
Edge Cases & Common Mistakes
- k equals the length: everything goes; return
"0", not an empty string. - Leading zeros:
"10200", k = 1 leaves"0200"; strip to"200". - Non-decreasing input: nothing is popped in the loop; the leftover removals must come off the end.
- Equal digits: do not pop on equal (
>not≥); removing one of two equal digits gains nothing there. - Converting to an integer: num can have up to 10⁵ digits; keep it as a string.
Summary
Walk the digits with a stack, popping a bigger top while removals remain, then push. Spend leftover removals on the end, strip leading zeros, and return "0" if nothing is left. O(n) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet