Remove K Digits to Make Smallest Number

Given a non-negative integer represented as a string and an integer k, remove k digits to make the number as small as possible.

Greedy Insight

Scan left to right. Whenever a digit is larger than the next digit, removing it makes the number smaller. This is because the leftmost mismatch has the highest impact.

"1432219", k=3
 ↑ 4 > 3 → remove 4 → "132219"
 ↑ 3 > 2 → remove 3 → "12219"
   ↑ 2 > 1 → remove 2 → "1219"

Solution

def remove_k_digits(num, k):
    """
    Remove k digits to form smallest number.
    Time: O(n), Space: O(n)
    """
    stack = []

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

    # If k digits still need removal (ascending sequence)
    while k > 0:
        stack.pop()
        k -= 1

    # Remove leading zeros and handle empty result
    result = ''.join(stack).lstrip('0')
    return result or '0'

Trace

Input: "1432219", k=3

digit | k | stack       | action
------|---|-------------|-------
1     | 3 | [1]         | push
4     | 3 | [1,4]       | push (4 > 1 but we want small, wait)
3     | 2 | [1,3]       | pop 4 (4>3), k=2, push 3
2     | 1 | [1,2]       | pop 3 (3>2), k=1, push 2
2     | 1 | [1,2,2]     | push (2 ≤ 2)
1     | 0 | [1,2,1]     | pop 2 (2>1), k=0, push 1
9     | 0 | [1,2,1,9]   | push (k=0, no more removals)

Wait — let me retrace more carefully:
1     | 3 | [1]         | push
4     | 3 | [1,4]       | push
3     | 2 | [1,3]       | pop 4, push 3
2     | 1 | [1,2]       | pop 3, push 2
2     | 1 | [1,2,2]     | push
1     | 0 | [1,2,1]     | pop 2, push 1 — wait k was 1

Let me be precise:

digit | k | stack         | action
------|---|---------------|-------
1     | 3 | [1]           | push
4     | 3 | [1,4]         | push (1 < 4, no pop)
3     | 3 | [1,4] → pop 4 | 4 > 3, pop, k=2 → [1,3]
2     | 2 | [1,3] → pop 3 | 3 > 2, pop, k=1 → [1,2]
2     | 1 | [1,2,2]       | 2 ≤ 2, push
1     | 1 | [1,2,2]→pop 2 | 2 > 1, pop, k=0 → [1,2,1]
9     | 0 | [1,2,1,9]     | k=0, push

Result: "1219"

Edge Cases

• k = len(num) — remove all digits, return "0"
• Ascending digits "1234" — remove from the end
• Leading zeros — "10200", k=1 → "200" (strip leading 0)
• All same digits — "1111", k=2 → "11"
• Single digit — k=1 → "0"

Complexity

Each digit is pushed once and popped at most once: O(n) time, O(n) space.

When to Use This Pattern

This “greedy removal with monotonic stack” pattern works when:

• You need to build the lexicographically smallest/largest result
• You can remove a fixed number of elements
• Left-to-right processing with backtracking on the last choice

Related Problems

• Remove Duplicate Letters (LeetCode 316) — smallest subsequence with unique chars
• Create Maximum Number (LeetCode 321) — two arrays version
• Monotone Increasing Digits (LeetCode 738)
• Most Competitive Subsequence (LeetCode 1673)