Remove K Digits — Monotonic Increasing Stack Greedy

Problem Statement#

Given string num representing a non-negative integer and an integer k, return the smallest possible integer after removing k digits from num.

Constraints:

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

Input:  num = "1432219", k = 3
Output: "1219"
Explanation: Remove 4, 3, and 2 (the three largest leading digits) → "1219"

Input:  num = "10200", k = 1
Output: "200" → but leading zeros removed → "200"
Wait: "10200" remove '1' → "0200" → strip → "200"
Actually: remove '1' is best since it gives "0200" → "200"

Input:  num = "10", k = 2
Output: "0"
Explanation: Remove both digits → "0" (never return empty string).

Why This Problem Matters#

LC 402 is a classic greedy + monotonic stack problem asked at Amazon, Google, and Microsoft. It teaches the fundamental insight behind many "construct smallest/largest number" problems:

• Greedy principle: To minimize a number, remove the leftmost digit that is greater than the next digit. The leftmost positions are most significant, so removing a larger digit there has the greatest impact.
• Monotonic increasing stack: Maintains digits in non-decreasing order, greedily removing any digit that exceeds the next incoming digit.

This pattern generalizes to: Create Maximum Number (LC 321), Remove Duplicate Letters (LC 316), and Largest Number (LC 179). Understanding Remove K Digits unlocks all of them.

The edge cases (leading zeros, leftover k after the loop, result being empty) make this problem a good test of careful coding.

The Core Insight#

Greedy insight: At each position, if the current digit is smaller than the digit to its left and we still have removals left (k > 0), removing the left digit decreases the number's value. We always prefer to remove a larger digit at a more significant (leftmost) position.

Monotonic increasing stack: Process digits left to right. For each digit d:

• While the stack top is greater than d and k > 0, pop the stack (remove that larger digit) and decrement k.
• Push d onto the stack.

After the loop:

• If k > 0 still, remove the last k digits (they are at the end, and since the stack is non-decreasing, the largest remaining digits are at the back).
• Strip leading zeros.
• Return "0" if the result is empty.

Visual Dry Run#

Input: num = "1432219", k = 3

Wait — let me redo: at '1' with stack ['1','2','2'] and k=1:

• top='2' > '1' and k>0: pop '2', k=0. Stack=['1','2'].
• top='2' > '1' but k=0: stop. Push '1'. Stack=['1','2','1'].

| '9' | 0 | ['1','2','1'] | k=0, push | ['1','2','1','9'] |

k=0 now. No trailing removal needed. Result: "1219". ✓

Input: num = "10200", k = 1

k=0 after loop. Stack: ['0','2','0','0']. No trailing removal. Strip leading zeros: "200". ✓

Solution (Optimal)#

# Python — monotonic increasing stack, O(n) time and space
def removeKdigits(num: str, k: int) -> str:
    stack = []  # monotonically non-decreasing stack of digits
 
    for d in num:
        # Greedily remove larger digits at higher positions
        while k > 0 and stack and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
 
    # If k removals still remain, remove from the end
    # (the stack is non-decreasing, so the largest remaining are at the back)
    if k > 0:
        stack = stack[:-k]
 
    # Strip leading zeros; if empty, return "0"
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

// JavaScript — monotonic increasing stack, O(n) time and space
function removeKdigits(num, k) {
    const stack = [];
 
    for (const d of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > d) {
            stack.pop();
            k--;
        }
        stack.push(d);
    }
 
    // Remove remaining k digits from the end
    if (k > 0) {
        stack.splice(stack.length - k, k);
    }
 
    // Strip leading zeros
    let result = stack.join('').replace(/^0+/, '');
    return result || '0';
}

Complexity:

Common Mistakes#

1. Forgetting to handle leftover k after the loop. If all digits are in non-decreasing order (e.g., "12345" with k=2), no pops occur in the loop — you must remove the last k digits afterward.

2. Not stripping leading zeros. After removing digits, the result may start with zeros (e.g., removing '1' from "10200" gives "0200" → should return "200"). Use lstrip('0') or equivalent.

3. Returning empty string instead of "0". If all digits are removed (k equals the length), lstrip('0') gives "". Always return "0" in this case: return result if result else '0'.

4. Using greater-than-or-equal (>=) for the pop condition. The problem does not say to remove equal digits — only larger ones. Using >= would incorrectly remove digits equal to the incoming digit when k > 0.

5. Decrementing k before checking k > 0. Always check k > 0 before attempting a pop. Decrementing below zero causes incorrect "free removals."

Interview Tips#

• State the greedy insight: "To minimize the number, I want to remove the leftmost digit that is larger than the digit to its right. A monotonic increasing stack does exactly this — whenever a smaller digit arrives, we greedily remove larger digits before it."
• Trace through "10200" explicitly to show leading-zero handling.
• Mention the three edge cases: (1) leftover k — remove from the end; (2) leading zeros — strip; (3) empty result — return "0".
• Compare with Remove Duplicate Letters (LC 316): "Same greedy stack approach, but there we also track whether each letter still appears later in the string."

Follow-up Questions#

1. Remove Duplicate Letters (LC 316) — same greedy stack but with additional count tracking to ensure each letter appears at least once.
2. Create Maximum Number (LC 321) — choose k digits from two arrays to form the largest number; uses the same monotonic stack idea but with a monotonic decreasing stack.
3. Largest Number (LC 179) — sort numbers by their concatenation order; different problem but related theme.
4. What if you want the largest number after removing k digits? Use a monotonic decreasing stack (pop when new digit is larger than top).
5. What if you can remove any digit (not just adjacent)? Greedy still works — the stack approach already handles non-adjacent comparisons.

Key Takeaways#

• Greedy principle: to minimize a number, remove the leftmost digit that is greater than the next digit — this is the most impactful removal at each step.
• A monotonic increasing stack implements this greedily: pop the stack top whenever a smaller digit arrives and removals (k) remain.
• After the loop, if k > 0, remove the last k digits (the stack is non-decreasing, so those are the largest remaining).
• Strip leading zeros after removal and return "0" for the empty string case.
• Each digit is pushed and popped at most once → O(n) time overall.
• This is the foundation of the "construct smallest/largest subsequence" family of problems in FAANG interviews.