Remove K Digits
Remove exactly k digits from a numeric string so the remaining number is the smallest possible.
Open on LeetCode ↗Intuition
The stack part of this problem is the easy half; nearly every wrong submission passes the pop logic and fails on the cleanup after. If the sweep never finds anything worth popping — the string is already non-decreasing, like "12345" — k removals still remain unspent, and they have to come off the end, where place value is lowest, not the front. Then the result can start with zeros the stack never stripped, and if k equals the string length the whole stack empties and returning an empty string is wrong. Sweep left to right with a stack, popping while the top exceeds the incoming digit and removals remain, and treat the cleanups as mandatory, not optional.
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
Find the highest-value removal
If digit d is immediately followed by a smaller digit, removing d promotes something smaller into a more significant position, which always lowers the number. Any digit followed by a larger one is better kept, since removing it would promote something bigger.
Enforce it with a monotonic stack
Push digits left to right. While the stack top is greater than the incoming digit and k > 0, pop and decrement k. Each pop is exactly the removal identified above, applied as early — and therefore as significantly — as possible.
Handle the leftovers
Three cleanups, and skipping any one fails a real test case. If k remains after the sweep, the string is non-decreasing, so remove from the end with st[:-k] — removing from the front is the mistake, since the front already passed through the pop logic. Strip leading zeros with lstrip('0'). If nothing survives, return "0" rather than an empty string. O(n) time, O(n) space.
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.