402. Remove K Digits - Explanation

1. Brute Force

Intuition

To make the smallest possible number, we want smaller digits to appear earlier.
If a digit is followed by a smaller digit, removing the larger one produces a smaller result.
We repeatedly find the first position where a digit is greater than its successor and remove it.
After k removals, we strip leading zeros and return the result.

Algorithm

Repeat the following k times:
- Scan from left to right to find the first digit that is greater than the next digit.
- Remove that digit from the string.
Strip any leading zeros from the result.
Return the remaining string, or "0" if it becomes empty.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        num = list(num)
        while k:
            i = 1
            while i < len(num) and num[i] >= num[i - 1]:
                i += 1
            num.pop(i - 1)
            k -= 1

        i = 0
        while i < len(num) and num[i] == '0':
            i += 1

        num = num[i:]
        return ''.join(num) if num else '0'

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(1)$ or $O(n)$ depending on the language.

2. Greedy + Stack

Intuition

The brute force approach rescans the string after each removal, which is inefficient.
A stack lets us make decisions in a single pass.
As we process each digit, we pop from the stack whenever the top is larger than the current digit and we still have removals left.
This greedily ensures that smaller digits bubble up to the front.

Algorithm

Initialize an empty stack.
For each character c in num:
- While k > 0, the stack is not empty, and the top of the stack is greater than c, pop from the stack and decrement k.
- Push c onto the stack.
If k is still greater than 0, remove k digits from the end of the stack.
Strip leading zeros from the result.
Return the final string, or "0" if empty.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for c in num:
            while k > 0 and stack and stack[-1] > c:
                k -= 1
                stack.pop()
            stack.append(c)

        while stack and k:
            stack.pop()
            k -= 1

        i = 0
        while i < len(stack) and stack[i] == '0':
            i += 1

        res = stack[i:]
        return ''.join(res) if res else "0"

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Two Pointers

Intuition

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.

Algorithm

Initialize l = 0 as the write pointer.
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.
Subtract any remaining k from l to trim excess digits from the end.
Skip leading zeros and return the substring from that point to l, or "0" if empty.

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'

Time & Space Complexity

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

Common Pitfalls

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.