Remove K Digits — Build the Smallest Number with a Monotonic Stack

Problem Statement#

Given string num representing a non-negative integer and an integer k, return the smallest number you can get by removing k digits from num. Return "0" if the result is empty.

Constraints:

• 1 <= k <= num.length <= 10^5
• num consists of only digits
• num does not have any leading zeros except for the zero itself

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

Input:  num = "10200", k = 1
Output: "200"

Why This Problem Matters#

Remove K Digits is one of the most elegant greedy problems in the medium tier. It teaches the core idea that drives several related problems: when building the smallest possible number from a sequence of digits, you want the digits in the result to be as small as possible, as early as possible. Whenever a larger digit appears before a smaller one, removing the larger one (if we have budget) produces a smaller number.

Amazon and Google frequently use this problem to test whether candidates understand the monotonic stack beyond "next greater element." Here, the stack is used constructively — it builds the answer rather than just computing a relationship. The answer is read directly from the stack contents.

The problem also has three subtle edge cases that all need correct handling: remaining budget after the loop, leading zeros, and empty result. Missing any one of these is an automatic fail in an interview.

The Core Insight#

Reducing a number to its smallest form by removing k digits is equivalent to: greedily remove any digit that is larger than the digit to its right, as long as we still have removals left.

Why? The digit 4 in 1432219 is larger than 3. Removing 4 turns it into 132219, which is smaller than any number we could get by removing a digit elsewhere. The leading digit dominates: a smaller leading digit always produces a smaller number regardless of what follows (assuming same length).

This leads to a monotonic increasing stack approach. Maintain an increasing stack. When a new digit d is smaller than the stack top, pop the top (we have budget and the current digit makes a smaller leading portion). After processing all digits, if k > 0, remove from the right (those are the rightmost digits in what is now a non-decreasing sequence).

Visual Dry Run#

Input: num = "1432219", k = 3

k=0 at end, no trailing trim. Result: "1219".

Solution (Optimal)#

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
 
        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
 
        # If k > 0, remove from the rightmost end
        if k > 0:
            stack = stack[:-k]
 
        # Strip leading zeros; return "0" if empty
        return ''.join(stack).lstrip('0') or '0'

var removeKdigits = function(num, k) {
    const stack = [];
 
    for (const digit of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
 
    if (k > 0) {
        stack.splice(stack.length - k, k);
    }
 
    const result = stack.join('').replace(/^0+/, '');
    return result || '0';
};

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

Common Mistakes#

• Popping without checking k > 0 — you must decrement k with each pop and stop when k reaches 0; otherwise you remove more digits than allowed
• Forgetting to trim from the right when k > 0 after the loop — for a non-decreasing input like "12345" with k=2, the loop never pops; you must remove 2 from the right
• Leading zeros in the result — after removing digits, the result may start with zeros; always lstrip('0') the result; return "0" not an empty string
• Comparing digits as characters — in Python '9' > '1' works correctly for single digit character comparisons; in JavaScript single character comparison is also valid

Interview Tips#

• Lead with the greedy insight: "Whenever we see a digit smaller than the one before it, removing the larger digit produces a smaller number. So I greedily pop from the stack when a smaller digit arrives, as long as I have budget."
• Walk through the three-phase answer construction explicitly: phase 1 (stack building with greedy pops), phase 2 (right-trim if k > 0), phase 3 (strip leading zeros and handle empty case).
• When asked "why remove from the right in phase 2?": "After the loop, the stack is non-decreasing. To minimize the number, keep the leftmost (smallest leading) digits and remove from the rightmost end."

Follow-up Questions#

• How does this relate to Remove Duplicate Letters (LC 316)? Both use a greedy monotonic stack. The difference: here the guard is budget-based (k pops allowed total); there the guard is last-occurrence-based.
• What if you want to create the LARGEST number by removing k digits? Reverse the comparison: use a decreasing stack (pop when a larger digit arrives). The same three-phase construction applies.
• Can you extend this to LC 321 Create Maximum Number? That requires combining two arrays — use two monotonic stacks plus a merge step comparing all possible split sizes.

Key Takeaways#

• Use a monotonic increasing stack: pop the stack top when a smaller digit arrives and you have budget (k > 0).
• Three-phase answer construction: stack building, right-trim if k > 0, strip leading zeros.
• The right-trim phase handles inputs that are already non-decreasing — the loop alone does not remove enough digits from these inputs.
• Leading zeros after removal are always stripped, and an empty result always returns "0".
• Decrement k with each pop and check k > 0 as a guard — without this guard you remove too many digits.
• This problem uses the stack constructively to build the answer rather than to compute a next-element relationship.
• The three edge cases (remaining budget, leading zeros, empty result) are the interview-critical details — missing any one of them fails specific test cases.