Remove K Digits

medium string stack greedy monotonic stack

Problem

Given a non-negative integer represented as a string num and an integer k, remove k digits to form the smallest possible number (also a string). Strip any leading zeros and return "0" if everything is removed.

Inputnum = "1432219", k = 3

Output"1219"

Each "drop" pops a digit from the stack whenever the next digit is smaller — making the result more left-heavy with small digits.

num

def remove_k_digits(num, k):
    stack = []
    for c in num:
        while k > 0 and stack and stack[-1] > c:
            stack.pop(); k -= 1
        stack.append(c)
    while k > 0: stack.pop(); k -= 1
    res = ''.join(stack).lstrip('0')
    return res or '0'

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

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && stack.peek() > c) {
                stack.pop(); k--;
            }
            stack.push(c);
        }
        while (k-- > 0 && !stack.isEmpty()) stack.pop();
        StringBuilder sb = new StringBuilder();
        for (Iterator<Character> it = stack.descendingIterator(); it.hasNext(); ) sb.append(it.next());
        int i = 0; while (i < sb.length() && sb.charAt(i) == '0') i++;
        String r = sb.substring(i);
        return r.isEmpty() ? "0" : r;
    }
}

string removeKdigits(string num, int k) {
    string st;
    for (char c : num) {
        while (k > 0 && !st.empty() && st.back() > c) { st.pop_back(); k--; }
        st.push_back(c);
    }
    while (k-- > 0 && !st.empty()) st.pop_back();
    int i = 0; while (i < (int)st.size() && st[i] == '0') i++;
    string r = st.substr(i);
    return r.empty() ? "0" : r;
}

Explanation

To make the smallest number, we want small digits as far left as possible, because the leftmost digits matter most. The trick is a greedy monotonic stack: go through the digits left to right and keep a stack that stays in increasing order.

For each new digit c, while we still have removals left (k > 0) and the digit on top of the stack is bigger than c, we pop it off. That bigger digit was hurting us by sitting to the left, so dropping it lets the smaller c shift left and shrink the number.

After scanning, if we still have removals left (k > 0), the stack is already increasing, so we just chop digits off the end. Finally we join the stack, strip any leading zeros, and return "0" if nothing is left.

Example: num = "1432219", k = 3. We push 1, then 4. At 3, top 4 > 3 so pop 4 (k=2), push 3. At 2, pop 3 (k=1), push 2. At 2, pop the earlier 2? No, it is equal not greater, so push. At 1, pop 2 (k=0). Then push the rest. Result is "1219".

Each digit is pushed and popped at most once, so this runs in one pass over the string.

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