Coding Patterns · Monotonic Increasing Stack

Leetcode 402: Remove K Digits

Use a monotonic increasing stack to remove larger earlier digits when a smaller digit arrives, producing the smallest possible number after k removals.

View Leetcode 402: Remove K Digits

Monotonic Increasing Stack Animation

Remove K Digits uses this idea: when a smaller digit arrives, remove larger digits before it.

digits
1
4
3
2
2
1
9
status
k left: 3answer so far: ∅
Start with an empty monotonic increasing stack. Smaller digits are better on the left.
∅
stack
Removed: ∅
Step 1 of 28 · speed 4000ms

The Intuition

Remove K Digits asks for the smallest possible number after deleting exactly k digits. The most important idea is this: digits on the left matter more than digits on the right.

If a smaller digit appears after a larger digit, and you still have removals left, remove the larger digit.

Example: in 43, removing 4 is better than removing 3, because 3 in the left position makes the whole number smaller.

That is why this problem uses a monotonic increasing stack. The stack tries to keep digits increasing from bottom to top. When the current digit is smaller than the stack top, the increasing rule is broken, so we pop.

Why Knowing The Pattern Is Not Enough

It is normal to still feel stuck even after hearing “use an increasing stack.” The missing step is understanding what the stack represents.

The stack is not just storing digits. It is storing the best number prefix we can build so far. Every time a new digit arrives, we ask: can this digit make the prefix smaller by removing something before it?

If yes, pop the larger digit. If no, push the current digit.

Walkthrough: num = 1432219, k = 3

Start with an empty stack. We want the smallest possible number after three removals.

  • Read 1. Stack is empty, so push it.
  • Read 4. Since 4 >= 1, push it.
  • Read 3. Since 3 < 4, pop 4. This makes the number smaller.
  • Read 2. Since 2 < 3, pop 3.
  • Read another 2. Since 2 >= 2, keep it and push.
  • Read 1. Since 1 < 2, pop one 2. Now k is zero, so we cannot pop anymore.
  • Push the remaining digits. The answer is 1219.

The Rule

While the stack is not empty, removals are still available, and the current digit is smaller than the stack top, pop.

java
while (
    stack.length > 0 &&
    k > 0 &&
    stack[stack.length - 1] > digit
) {
    stack.pop();
    k--;
}

After that loop stops, push the current digit.

Java Solution

java
class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char digit : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > digit) {
                stack.pop();
                k--;
            }

            stack.push(digit);
        }

        while (!stack.isEmpty() && k > 0) {
            stack.pop();
            k--;
        }

        StringBuilder sb = new StringBuilder();

        while (!stack.isEmpty()) {
            sb.append(stack.removeLast());
        }

        while (sb.length() > 0 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Why The End Cleanup Exists

Sometimes the digits never decrease enough to trigger pops. For example, with 12345, the stack stays increasing the whole time.

If k is still greater than zero after the loop, remove digits from the end. Those are the least valuable positions to keep because they are farthest to the right.

Complexity

Time complexity is O(n) because each digit is pushed once and popped at most once. Space complexity is O(n) for the stack.