Remove K Digits
Remove exactly k digits from a numeric string so the remaining number is the smallest possible.
- 1 <= k <= num.length <= 10⁵
- num consists of only digits.
- num does not have any leading zeros except for the zero itself.
Intuition
Remove k digits deletes exactly k digits from a number to leave the smallest possible result, preserving the order of the digits that remain.
The governing insight is about position, not magnitude. A digit's contribution depends on where it sits, so removing a digit early in the number matters far more than removing a large digit later:
- Whenever a digit is followed by a smaller one, removing it shrinks the number — so scan left to right and delete any digit larger than its successor.
That is a monotonic increasing stack. Push digits, and before pushing, pop any stacked digit greater than the incoming one while removals remain.
Each pop is one of the k removals, and the greedy is optimal because removing a larger digit from an earlier position always beats removing anything later.
Three finishing steps decide correctness, and each is a common failure:
If removals remain after the scan — which happens when the digits are already non-decreasing, as in "12345" — remove from the end, since the trailing digits are the largest positionally.
Strip leading zeros from the result. Removing digits can expose zeros at the front, and "0200" must be returned as "200".
If everything is removed or only zeros remain, return "0" rather than an empty string.
The result length is always n − k, which is a useful check while building.
Each digit is pushed and popped at most once, giving O(n) time and O(n) space for the stack.
To make the smallest number, remove any digit that is larger than the one following it — a monotonic increasing stack does exactly that. Leftover budget after the scan means the remaining digits already ascend, so the largest ones at the tail get trimmed.
Approach
Before reading on: price up what the direct approach costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for O(n) time and O(n) space.
Reason about position, not size
A digit's value depends on where it sits, so removing a large digit early beats removing a larger one later. That is what makes the greedy correct.
Pop before pushing
Scan left to right and pop any stacked digit greater than the incoming one while removals remain. Each pop uses one of the k deletions.
Maintain an increasing stack
The stack stays non-decreasing, which is precisely the shape of the smallest achievable number for the digits kept so far.
Remove leftovers from the end
If removals remain after the scan, trim from the end. This happens on already-increasing input like "12345", where no pops occur.
Strip leading zeros
Deletions can expose zeros at the front. "0200" must be returned as "200" — the strip is not optional.
Return zero for an empty result
If every digit is removed or only zeros remain, return "0", not an empty string.
Cost of the approach
Each digit is pushed and popped at most once, giving O(n) time and O(n) space for the stack.
Solution & live demo
Common pitfalls
Not spending leftover k
res = ''.join(st).lstrip('0')if k:
st = st[:-k]If the input is already non-decreasing, no pops happen and k removals are still owed. The digits ascend, so the largest are at the end and trimming the tail is optimal.
Returning an empty string
return ''.join(st).lstrip('0')return res or '0'
Removing every digit, or leaving only zeros, strips down to nothing — but the expected output for zero is "0". The fallback is easy to forget because it only triggers on a few inputs.
Popping on >=
while k and st and st[-1] >= ch:
while k and st and st[-1] > ch:
Removing a digit equal to the next one changes nothing about the number's value but wastes a removal from the budget, so a genuinely useful removal later can't be made.
Edge cases
Everything is removed, so return "0".
Strip them — the answer is "200", not "0200".
No pops fire, so the trailing removal path handles all of k.
Stripping empties the string, so the explicit "0" fallback is required.