Remove K Digits

Medium Monotonic Stack Monotonic Stack Original on LeetCode

Remove K Digits is a medium monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (monotonic stack), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (remove one digit at a time) up.

Problem

You are given a non-negative integer as a string num and an integer k. Delete exactly k digits from num so that the number formed by the remaining digits, in their original order, is as small as possible.

Return that smallest number as a string without leading zeros. If no digits remain, return "0".

Examples

Example 1

Input
num = "52816", k = 2
Output
216
Why
Dropping 5 and 8 leaves 216. Every other pair of deletions leaves a larger 3-digit number, such as 516 or 281.

Example 2

Input
num = "30045", k = 1
Output
45
Why
Removing the leading 3 leaves "0045", which is written without leading zeros as 45.

Example 3

Input
num = "77", k = 2
Output
0
Why
All digits are removed, and an empty result counts as 0.

Constraints

  • 1 <= k <= num.length <= 10^5
  • num contains only the digits 0-9.
  • num has no leading zeros, except when it is exactly "0".

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (remove one digit at a time)O(n · k)O(n)
Optimal (monotonic stack)O(n)O(n)

1Brute force (remove one digit at a time)

TimeO(n · k)Each of the k rounds scans and shifts up to n characters.
SpaceO(n)A mutable copy of the digits.

To lower a number most by deleting one digit, delete the first digit that is larger than its right neighbor (a "peak"); if the digits never decrease, delete the last one. Repeat this k times, then remove leading zeros.

  1. Repeat k times: find the first i with num[i] > num[i+1]; delete it, or delete the last digit if there is no such i.
  2. Strip leading zeros from what is left.
  3. Return the result, or "0" if it is empty.
class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder(num);
        for (int r = 0; r < k; r++) {
            int i = 0;
            while (i + 1 < sb.length() && sb.charAt(i) <= sb.charAt(i + 1)) i++;
            sb.deleteCharAt(i);
        }
        int start = 0;
        while (start < sb.length() && sb.charAt(start) == '0') start++;
        String res = sb.substring(start);
        return res.isEmpty() ? "0" : res;
    }
}

2Optimal (monotonic stack)

TimeO(n)Each digit is pushed once and popped at most once.
SpaceO(n)The stack can hold all n digits.

Scan the digits once while keeping a stack of the digits chosen so far. Whenever the new digit is smaller than the top of the stack and removals remain, the top is a peak: popping it makes the number smaller, so pop and spend one removal. The stack stays non-decreasing. Leftover removals come off the end, which holds the largest digits.

  1. For each digit d: while k > 0, the stack is non-empty and its top > d, pop and k--. Then push d.
  2. While k > 0, pop from the end and k--.
  3. Skip leading zeros at the bottom of the stack and build the string.
  4. Return it, or "0" if it is empty.
class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder st = new StringBuilder();
        for (char d : num.toCharArray()) {
            while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > d) {
                st.deleteCharAt(st.length() - 1);
                k--;
            }
            st.append(d);
        }
        st.setLength(st.length() - k);
        int start = 0;
        while (start < st.length() && st.charAt(start) == '0') start++;
        String res = st.substring(start);
        return res.isEmpty() ? "0" : res;
    }
}

Edge cases to test

  • k equals the length: the answer is "0"
  • Digits already in non-decreasing order, like "12345": remove from the end
  • Removing a digit exposes leading zeros, which must be stripped
  • Long runs of equal digits, like "11111"

Hints

Hint 1

Which single digit should go to make the number as small as possible? Look for the first position where a digit is bigger than the one after it.

Hint 2

Applying that rule k times works but rescans the string each time. Can you process the digits left to right just once?

Hint 3

Keep a stack of kept digits. Before pushing a new digit, pop bigger digits from the top while you still have removals left. Use any leftover removals on the end, then strip leading zeros.

FAQ

What is the best time complexity for Remove K Digits?

Optimal (monotonic stack) runs in O(n) time and O(n) extra space. Each digit is pushed once and popped at most once.

Which pattern does Remove K Digits use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.

Is there a brute force solution for Remove K Digits?

Yes. Brute force (remove one digit at a time) takes O(n · k) time and O(n) space. To lower a number most by deleting one digit, delete the first digit that is larger than its right neighbor (a "peak"); if the digits never decrease, delete the last one.

Which edge cases should I test for Remove K Digits?

k equals the length: the answer is "0"; Digits already in non-decreasing order, like "12345": remove from the end; Removing a digit exposes leading zeros, which must be stripped; Long runs of equal digits, like "11111".