Remove K Digits — Monotonic Increasing Stack

Problem 265 · Remove K Digits

Difficulty: Medium · Pattern: Monotonic Increasing Stack

Remove k digits to form the smallest possible number.

Intuition

Maintain a monotonic increasing stack. When a digit is smaller than the top and k > 0, pop (remove) the larger digit. Handle leading zeros and remaining k.

Solutions

# Python
def removeKdigits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop(); k -= 1
        stack.append(d)
    # If k remaining, remove from end (already sorted)
    stack = stack[:-k] if k else stack
    return ''.join(stack).lstrip('0') or '0'

// Java
public String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char d : num.toCharArray()) {
        while (k > 0 && !stack.isEmpty() && stack.peek() > d) { stack.pop(); k--; }
        stack.push(d);
    }
    while (k-- > 0) stack.pop();
    StringBuilder sb = new StringBuilder();
    boolean leadZero = true;
    // stack is in reverse order
    String s = stack.stream().map(String::valueOf).reduce("", (a,b)->b+a);
    s = new StringBuilder(s).reverse().toString();
    s = s.replaceFirst("^0+", "");
    return s.isEmpty() ? "0" : s;
}

# Python (clean)
def removeKdigits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop(); k -= 1
        stack.append(d)
    return (''.join(stack[:len(stack)-k]).lstrip('0') or '0')

Complexity

Time: O(n)
Space: O(n)