Remove K Digits (LeetCode 402)

The problem

You get a non-negative integer as a string num and an integer k. Remove exactly k digits so the remaining digits, kept in their original order, form the smallest possible number. Return it as a string with no leading zeros, or "0" if nothing is left.

Input:  num = "1432219", k = 3
Output: "1219"

Removing 4, 3 and one 2 leaves 1219. Any other choice of three digits gives a bigger number.

How to think about it

Start with brute force. Try every way to choose k digits to delete and keep the smallest result. That is C(n, k) options, which explodes. Even a smarter “remove one digit at a time, try every position” approach is O(k · n²) once you count rebuilding strings.

What makes one number smaller than another of the same length? The leftmost digit where they differ. So the most important thing is to make the first digit as small as possible, then the second, and so on. A small digit early beats any savings later.

The key insight: a digit followed by a smaller digit should go. If you see ...4 3..., deleting the 4 moves the 3 into its place, making that position smaller. That is always a win. So scan left to right with a stack of kept digits. When the next digit d is smaller than the top, and you still have deletions left, pop the top (delete it) and check again. Then push d. The kept digits end up in non-decreasing order, which is an increasing monotonic stack.

Leftover deletions come off the end. If the scan finishes with k > 0, the stack is non-decreasing, so the largest digits are at the end. Chop the last k. Finally strip leading zeros.

Which pattern is this? Greedy with a monotonic stack. The tell is “remove elements to make the sequence lexicographically smallest while keeping order”.

Approach

1. Create an empty stack st.
2. For each digit d in num:
   • While st is non-empty, k > 0, and st[-1] > d: pop and decrement k.
   • Push d.
3. If k is still positive, drop the last k digits from the stack.
4. Join the stack, strip leading zeros, and return "0" if the result is empty.

Solution

def remove_k_digits(num, k):
    st = []
    for d in num:
        while st and k and st[-1] > d:    # a smaller digit can move left
            st.pop(); k -= 1
        st.append(d)
    st = st[:len(st)-k] if k else st      # unused removals: cut the largest tail
    return "".join(st).lstrip('0') or "0"
# remove_k_digits("1432219", 3) -> "1219"

Dry run

On num = "1432219", k = 3:

k reached 0, so nothing is trimmed. No leading zeros, so the answer is “1219”.

Complexity

• Time: O(n). Each digit is pushed once and popped at most once. The final join and strip are O(n).
• Space: O(n). The stack holds up to n digits.

Edge cases and pitfalls

• Leading zeros: "10200", k = 1 pops the 1 and leaves "0200", which must become "200".
• Everything removed: "10", k = 2 leaves an empty string. Return "0", not "".
• Already non-decreasing input like "12345", k = 2 pops nothing in the loop; the tail trim gives "123".
• Don’t use st[:-k] blindly: when k == 0, st[:-0] is an empty list. The if k else st guard handles that.
• Comparing characters works for digits because '0' < '1' < … < '9', so there’s no need to convert to integers.

Related problems

• Daily Temperatures (LeetCode 739): the core “pop while the new element beats the top” loop.
• Largest Rectangle in Histogram (LeetCode 84): another increasing stack, popping when a smaller value arrives.
• Asteroid Collision (LeetCode 735): a stack where each new element may destroy several on top.