Remove K Digits: Monotonic Stack Greedy

LeetCode's Remove K Digits (problem 402) asks you to remove exactly k digits from a number string to produce the smallest possible result. It is rated medium and combines two patterns you will see repeatedly in interviews: monotonic stacks and greedy choices. Once you see why removing a "peak" digit always helps, the algorithm writes itself.

The approach: greedy removal with a monotonic stack

The key insight is this: to make the number as small as possible, you want the leftmost digits to be as small as possible. Whenever you see a digit that is larger than the digit right after it, removing that larger digit always produces a smaller number. You keep doing this until you have removed k digits.

A stack is the perfect tool for this. You process digits left to right, and before pushing a new digit, you pop any stack top that is larger than the current digit (as long as you still have removals left). This naturally keeps the stack in non-decreasing order, which is exactly the condition for the smallest number.

Here is the full algorithm:

• Initialize an empty stack and walk through each digit in the string.
• While the stack is not empty, the top of the stack is greater than the current digit, and k is greater than 0: pop the stack and decrement k.
• Push the current digit onto the stack.
• If k is still greater than 0 after processing all digits, remove the last k digits from the stack (they are the largest remaining ones at the tail).
• Strip leading zeros from the result. If the result is empty, return "0".

def removeKdigits(num, k):
    stack = []

    for digit in num:
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    if k > 0:
        stack = stack[:-k]

    return "".join(stack).lstrip("0") or "0"

Complexity

Each digit is pushed onto the stack at most once and popped at most once. The total number of push and pop operations across the entire loop is at most 2n, so the algorithm runs in O(n) time. The stack holds at most n digits, giving O(n) space.

The building blocks

Monotonic stack pop loop. The core pattern is the same one you see in Daily Temperatures and Largest Rectangle in Histogram. You compare the current element against the stack top and pop while a condition holds. For Remove K Digits, the condition is stack[-1] > digit and k > 0. The only difference from other monotonic stack problems is the removal budget: you stop popping once k reaches 0, even if the stack top is still larger.

Greedy left-to-right digit selection. The greedy principle here is that the most significant (leftmost) positions matter the most. A smaller digit in position 0 always beats a smaller digit in position 5, no matter what. By scanning left to right and removing peaks as you encounter them, you guarantee that each position ends up with the smallest digit it can have given the removal budget. This same greedy logic appears in problems like Remove Duplicate Letters, where you also use a stack to build the lexicographically smallest result.

Leading zero cleanup. After the stack produces the raw result, you need to strip any leading zeros. This is a small detail that is easy to forget under pressure. The lstrip("0") call handles it, and the or "0" ensures you do not return an empty string when all digits are removed.

Edge cases

• k equals the length of the string. Every digit gets removed. The answer is "0". The stack[:-k] slice produces an empty list, and or "0" handles it.
• Already the smallest possible. If the digits are already in non-decreasing order (like "1234"), no pops happen during the loop. The last k digits get trimmed from the tail instead.
• Leading zeros after removal. Input "10200" with k=1 removes the '1', leaving "0200". After stripping leading zeros, the result is "200".
• All same digits. Input "1111" with k=2 removes two digits from the tail (no pops happen). Result is "11".

From understanding to recall

The algorithm itself is short, but there are a few details that trip people up under pressure. The while loop has three conditions (stack not empty, k greater than 0, top greater than current), and forgetting any one of them causes bugs. The post-loop cleanup for remaining k and leading zeros are both easy to overlook if you have not practiced recently.

What makes this problem a good candidate for repeated practice is that the logic is compact enough to write in under five minutes, but the edge cases (leading zeros, k equals length, already sorted input) require careful handling. Each time you practice, you reinforce the full picture: the pop loop, the tail trim, and the cleanup.

Spaced repetition helps you move past the "I solved it once" stage into genuine fluency. After a few reps at increasing intervals, you will not need to re-derive the algorithm. You will just write it.

Related posts

• Remove Duplicate Letters - Uses the same monotonic stack and greedy pattern to build the lexicographically smallest string with unique characters
• Daily Temperatures - The classic introduction to monotonic stacks, using the same pop-when-condition-holds loop with a simpler computation
• Largest Rectangle in Histogram - Another monotonic stack problem where the pop triggers an area calculation instead of a removal