Skip to content

Remove K Digits

A New Role for the Stack

Up to this point, you've used the monotonic stack as a query tool. You scanned an array, maintained the stack, and extracted information — boundaries, nearest greater elements, histogram widths. The stack helped you answer questions about the data.

Now the stack gets a promotion. It's going to build the answer.

The problem we're starting with is a classic: given a string of digits representing a non-negative integer, remove exactly K digits so the remaining number is as small as possible. Return that number as a string.

For example, if num = "1432219" and K = 3, the answer is "1219".

Seems simple enough. But the brute force — trying all combinations of digits to remove — is exponential. We need something smarter.

The Greedy Insight

Think about what makes a number small. The leftmost digits matter most. The number 1999 is smaller than 2000, even though every other digit in 1999 is larger. So to minimize the result, you want the leftmost positions to hold the smallest possible digits.

Here's the key observation. Scan left to right. If you ever see a digit that's followed by a smaller digit, removing the larger one improves the number. Why? Because the smaller digit slides left into a more significant position.

Look at "1432219". The 4 is followed by 3. Removing the 4 gives "132219" — that's better than keeping it. Now the 3 is followed by 2. Removing the 3 gives "12219". The first 2 is followed by another 2, so that's fine. The second 2 is followed by 1 — remove it to get "1219".

Does this pattern ring a bell? A larger element sitting in front of a smaller one — that's a chain disturbance. The smaller element "eclipses" the larger one. This is exactly the logic that drives a monotonic increasing stack. When a new element arrives that's smaller than the stack top, the top gets popped.

But There's a Catch

In a standard monotonic stack, you pop freely. Every disturbance gets resolved. Here you can't do that — you only get to remove K digits total. You have a limited number of pops.

Think of K as a pop budget. Every time you pop an element from the stack, you spend one unit of budget. Once the budget hits zero, you stop popping and just push everything that comes next, no matter what.

This single constraint — a finite pop budget — is what transforms the standard monotonic stack into a greedy construction algorithm.

Full Walkthrough: "1432219", K = 3

Let's trace through this carefully. We'll maintain a stack (really a string we're building), and track the remaining budget.

Budget: 3

  1. Digit '1' arrives. Stack is empty. Push it. Stack: [1] | Budget: 3

  2. Digit '4' arrives. 4 > 1, no disturbance. Push. Stack: [1, 4] | Budget: 3

  3. Digit '3' arrives. 3 < 4 — disturbance! Pop the 4. Budget drops to 2. Now check: 3 > 1, no more disturbance. Push 3. Stack: [1, 3] | Budget: 2

  4. Digit '2' arrives. 2 < 3 — pop the 3. Budget drops to 1. Check: 2 > 1, stop. Push 2. Stack: [1, 2] | Budget: 1

  5. Digit '2' arrives. 2 >= 2 — no disturbance. Push. Stack: [1, 2, 2] | Budget: 1

  6. Digit '1' arrives. 1 < 2 — pop a 2. Budget drops to 0. Now 1 < 2, but budget is 0, can't pop anymore. Push 1. Stack: [1, 2, 1] | Budget: 0

  7. Digit '9' arrives. Budget is 0. Just push. Stack: [1, 2, 1, 9] | Budget: 0

Result: "1219". That's correct.

Step-by-step trace of Remove K Digits on "1432219" with K=3

Notice what happened. The stack greedily tried to maintain an increasing sequence, but it could only fix K disturbances. After the budget ran out, it accepted whatever came next.

The Algorithm

Here it is in plain terms:

Initialize an empty stack (or string).
For each digit in the input:
    While budget > 0 AND stack is not empty AND stack top > current digit:
        Pop the stack top.
        Decrement budget.
    Push the current digit.
If budget > 0 after processing all digits:
    Remove the last 'budget' characters from the stack.
Strip leading zeros.
If the result is empty, return "0".

That's it. One pass, O(N) time. The while loop might look like it could blow up, but each digit is pushed and popped at most once, so the total work across all iterations is O(N).

Edge Cases That Bite

There are a few edge cases that trip people up. Let's handle them now.

Leftover budget

If the input is already non-decreasing — like "12345" with K = 2 — no pops happen during the scan. The budget stays full. In this case, you remove from the end of the stack. Chopping "12345" down to "123" is correct: the smallest number comes from keeping the leftmost digits when everything is already sorted.

This is why the algorithm has that final step: "if budget > 0, remove the last budget characters."

Leading zeros

Consider num = "10200", K = 1. After removing the 1 (it's followed by 0, which is smaller), the stack holds "0200". That's really just "200". You need to strip leading zeros from the result.

But be careful — don't strip all the zeros. If the result is "0" (like num = "10", K = 1), you should return "0", not an empty string.

All digits removed

If K equals the length of the string, every digit gets removed. Return "0".

Equal digits

When the current digit equals the stack top, we do not pop. Popping 5 to replace it with another 5 wastes a budget unit for no gain. The condition is strictly stack.back() > current, not >=.

Connecting Back to Chapter 1

Remember the four variants from Chapter 1 — NGE, NSE, PGE, PSE? Those were about finding the nearest element that breaks the chain. Here, we're not just finding the break — we're acting on it by removing the offending element. And we're doing it with a limited number of actions.

The monotonic stack's core behavior hasn't changed. Elements that maintain the desired order stay. Elements that violate it get ejected. The only new idea is that ejections are rationed.

Why This Works

Here's the informal argument for correctness. At each step, we make the locally optimal choice: if the current digit can improve the number by replacing a larger digit to its left, we make that swap (by popping and pushing). We never regret these swaps because:

  1. We process left to right, so we're always fixing the most significant position first.
  2. A pop only happens when it strictly improves the sequence (the new digit is smaller).
  3. The budget ensures we don't overshoot — we remove exactly K digits total.

This greedy approach gives the globally optimal answer. You can prove it by exchange argument: if the optimal solution differs from ours at some position, swapping to our choice can only improve or maintain the result.

What's Next

The pop budget idea is more general than it looks. In the next lesson, we'll strip away the "digits" specifics and see that this same pattern solves a whole family of problems: finding the lexicographically smallest (or largest) subsequence of any given length.