☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Remove K Digits

Medium TUF ID 970 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a non-negative integer as a string num and an integer k. Delete exactly k digits from num (the remaining digits keep their order) so that the resulting number is as small as possible. Return it as a string without leading zeros; if nothing is left, return "0".

Constraints: 0 ≤ k ≤ n ≤ 10^5, num consists of digits only and has no leading zeros except for the number "0" itself. The string can be far longer than any numeric type, so all reasoning must be done on digits, never by converting to long.

Example 1

num = "1432219", k = 3
answer = "1219"     // remove 4, 3 and the second 2

Example 2

num = "10200", k = 1
answer = "200"      // removing 1 leaves "0200"; leading zeros are dropped

Example 3

num = "10", k = 2
answer = "0"        // everything is removed

The key observation. After removing exactly k digits, every candidate has the same length n - k. Two numbers of the same length are compared digit by digit from the left, and the first difference decides. So a smaller digit early on beats anything that happens later. We want the leftmost digits to be as small as possible, greedily.

Approach 1: Brute force, remove one “peak” at a time

Intuition. Think about removing a single digit. Walk from the left while the digits are non-decreasing. The first time a digit is greater than the digit after it (a “peak”), remove it: the digit that slides into its place is smaller, and every digit before it is untouched, so the number gets smaller at the earliest possible position.

Why not remove an earlier digit? Before the peak the digits are non-decreasing, so removing one of them pulls a digit that is equal or larger one place left, which can only make the number bigger or keep it equal. Why not a later digit? Then the peak itself stays in place while the alternative would have replaced it with a smaller digit. If there is no peak at all (the string is non-decreasing, like "112"), the best single removal is the last digit, since the largest digits are at the end.

Repeating this best single removal k times gives the best k removals. An exchange argument shows that some optimal set of k deletions always includes the first peak, so taking it first never closes off the optimum.

Algorithm.

  1. Repeat k times:
    • Find the first index i with num[i] > num[i + 1]; if none exists, i is the last index.
    • Delete the digit at i.
  2. Strip leading zeros; return "0" if the string is empty.
static String bruteForce(String num, int k) {
    StringBuilder sb = new StringBuilder(num);
    for (int round = 0; round < k; round++) {
        int i = 0;
        while (i + 1 < sb.length() && sb.charAt(i) <= sb.charAt(i + 1)) i++;
        sb.deleteCharAt(i);                       // first "peak", or the last digit if the string is non-decreasing
    }
    return stripLeadingZeros(sb);
}

static String stripLeadingZeros(StringBuilder sb) {
    int i = 0;
    while (i < sb.length() && sb.charAt(i) == '0') i++;
    String s = sb.substring(i);
    return s.isEmpty() ? "0" : s;
}

Complexity. Time O(n · k): each round scans up to n digits, and deleteCharAt shifts up to n characters. Space O(n) for the builder. With n = k = 10^5 this is around 10^10 operations, too slow.

The waste is obvious: after deleting a peak, the next round starts scanning from index 0 again, even though the prefix before the deleted digit was already known to be non-decreasing.

Approach 2: Optimal, monotonic stack

Intuition. Keep the digits we have decided to keep in a stack. Read num from left to right. When the new digit c is smaller than the top of the stack, the top is exactly the “first peak” of what we have so far: it is followed by something smaller. Removing it is the best single deletion, so pop it, spend one deletion, and compare c with the new top. Keep popping while the top is larger than c and deletions remain. Then push c.

The stack is always non-decreasing from bottom to top, which is the same invariant the brute force rediscovers on every rescan. The stack simply never forgets it.

Two things can be left over at the end:

Note the comparison is strict (>). Equal digits are not a peak; popping a 3 to push another 3 spends a deletion and changes nothing.

Algorithm.

  1. For each digit c:
    • While k > 0, the stack is not empty, and top > c: pop and decrement k.
    • Push c.
  2. Remove the last k digits of the stack.
  3. Strip leading zeros; return "0" if empty.

A StringBuilder works as a stack of characters: append is push, and deleteCharAt(length - 1) is pop, both O(1) because nothing needs to shift.

static String optimal(String num, int k) {
    StringBuilder st = new StringBuilder();      // used as a stack of digits
    for (char c : num.toCharArray()) {
        while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > c) {
            st.deleteCharAt(st.length() - 1);
            k--;
        }
        st.append(c);
    }
    st.setLength(st.length() - k);               // deletions still owed come off the end
    return stripLeadingZeros(st);
}

Dry run on num = "1432219", k = 3:

digit pops (k after) stack after
1 none (3) 1
4 none (3) 14
3 pop 4 (2) 13
2 pop 3 (1) 12
2 none, 2 is not > 2 (1) 122
1 pop 2 (0) 121
9 none, k is 0 (0) 1219

No deletions are left over and there are no leading zeros, so the answer is "1219".

Complexity. Time O(n): every digit is pushed once and popped at most once, and stripping zeros is one more pass. Space O(n) for the stack.

setLength(st.length() - k) never goes negative. The loop pops only while k > 0, so after it the stack holds n - (k_original - k) digits, which is at least k because k_original ≤ n.

Edge cases and pitfalls