Remove K Digits

Problem

Given a non-negative integer as a string and an integer k, remove k digits so the remaining number is as small as possible. Return that number (no leading zeros, return "0" if empty).

Constraints

• 1 ≤ k ≤ num.length ≤ 10⁵

Approach — Monotonic Stack

This is a Monotonic Stack problem. The idea: scan once and keep a stack whose order stays meaningful, popping elements as soon as a later value resolves them. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def removeKdigits(self, num, k):
        st = []
        for d in num:
            while k and st and st[-1] > d:
                st.pop(); k -= 1
            st.append(d)
        st = st[:len(st)-k] if k else st
        return ''.join(st).lstrip('0') or '0' 

Java

import java.util.*;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.