Remove K Digits — Solution

Problem

Given a string of digits and an integer k, delete exactly k digits so that the remaining number is as small as possible. Leading zeros should be omitted from the result, and if all digits are removed return "0".

• Input: num = "1432219", k = 3
• Output: "1219"
• Explanation: Removing the 4, 3, and 2 yields the smallest possible number.

A counter-example to show why "just remove the k largest digits" is wrong: in "1432219" the three largest digits are 9, 4, 3 — removing them gives "1221", which is bigger than "1219". Position matters more than size.

Intuition

A large digit sitting before a smaller digit inflates the number — replacing it with the smaller digit brings the number down faster than any later removal can. Scanning left to right and greedily popping any stack-top digit that is larger than the current digit (while removals remain) always produces the smallest possible prefix.

Solution — Monotonic Stack

Maintain a stack that stays non-decreasing from bottom to top. For each new digit, evict any stack-top digit that is larger, spending one removal per eviction. Once the loop ends, if removals remain the stack is already non-decreasing, so trim from the right. Strip leading zeros from whatever is left.

1. Initialize an empty stack.
2. For each digit in num, while k > 0, the stack is non-empty, and the stack top exceeds the current digit, pop and decrement k.
3. Push the current digit.
4. After the loop, if k > 0, truncate the stack by removing k elements from the right end.
5. Strip leading zeros, keeping at least one character.
6. Return the result string, or "0" if it is empty.

1def removeKdigits(num: str, k: int) -> str:
2    stack = []
3    for digit in num:
4        # Evict any larger digit that comes before a smaller one
5        while k > 0 and stack and stack[-1] > digit:
6            stack.pop()
7            k -= 1
8        stack.append(digit)
9    # If removals remain, the stack is non-decreasing — trim from the right
10    if k > 0:
11        stack = stack[:-k]
12    result = ''.join(stack).lstrip('0')
13    return result or '0'

Time: O(n) — each digit is pushed and popped at most once. Space: O(n) — the stack holds at most n digits.

Complexity Summary

Common Mistakes

• Forgetting to trim when k > 0 after the loop — if the input is already non-decreasing (e.g. "12345"), no pops fire and you must still remove k digits from the right end.
• Off-by-one with stack[:-k] in Python when k is 0 — some_list[:-0] evaluates to [], emptying the list. Guard the slice with if k > 0.
• Not stripping leading zeros — removing a digit before a zero exposes it (e.g. "10200", k=1 → pop '1' → "0200" → must return "200").
• Returning "" instead of "0" — when every digit is removed or stripped as a leading zero, the correct answer is "0", not an empty string.
• Using push/peek/pop in Java's Deque — these operate on the front of the deque and reverse the digit order; use addLast/peekLast/pollLast to maintain left-to-right ordering.

Related Problems

• largest-rectangle-in-histogram — uses a monotonic increasing stack to find the widest rectangle bounded by each bar
• daily-temperatures — classic monotonic stack to find the next warmer day for each index
• next-greater-element-ii — monotonic stack extended to a circular array
• sum-of-subarray-minimums — monotonic stack to count how many subarrays each element is the minimum of
• next-permutation — greedy digit rearrangement to produce the lexicographically next larger number