Remove K Digits

How it works

Instead of using a separate stack, we can simulate stack behavior in place using two pointers. The left pointer l represents the top of our virtual stack, while the right pointer r scans through the input. When we see a smaller digit, we backtrack l to remove larger digits, then place the current digit. This achieves the same greedy logic with better space efficiency.

Steps

1. Initialize l = 0 as the write pointer.
2. For each index r from 0 to the end of num:
   • While l > 0, k > 0, and num[l-1] > num[r], decrement both l and k.
   • Write num[r] at position l and increment l.
3. Subtract any remaining k from l to trim excess digits from the end.
4. Skip leading zeros and return the substring from that point to l, or "0" if empty.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) or O(n) depending on the language.

Things to watch for

Forgetting to Remove Remaining Digits When k > 0

After processing all digits, there may still be removals left if the string was already in non-decreasing order (e.g., "12345" with k=2). If you do not trim the last k digits from the result, you will return a number larger than necessary. Always check if k > 0 after the main loop and remove digits from the end accordingly.

Not Stripping Leading Zeros

Removing digits can expose leading zeros that make the result invalid (e.g., removing 1 from "10200" leaves "0200"). Failing to strip these zeros results in incorrect output. After all removals, scan from the start and skip any '0' characters before constructing the final string.

Returning an Empty String Instead of "0"

When all digits are removed or only zeros remain after stripping, the result should be "0", not an empty string. For example, "10" with k=2 should return "0". Always check if the final string is empty and return "0" as a fallback to handle this edge case.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        l = 0
        num = list(num)

        for r in range(len(num)):
            while l > 0 and k > 0 and num[l - 1] > num[r]:
                l -= 1
                k -= 1
            num[l] = num[r]
            l += 1

        l -= k
        i = 0
        while i < l and num[i] == '0':
            i += 1
        res = ''.join(num[i:l])
        return res if res else '0'

class Solution {
public:
    string removeKdigits(string num, int k) {
        int l = 0;
        for (int r = 0; r < num.size(); r++) {
            while (l > 0 && k > 0 && num[l - 1] > num[r]) {
                l--;
                k--;
            }
            num[l++] = num[r];
        }

        l -= k;
        int i = 0;
        while (i < l && num[i] == '0') {
            i++;
        }
        if (i == l) return "0";
        return num.substr(i, l - i);
    }
};