LeetCode 402: Remove K Digits

Problem Restatement

We are given a string num representing a non-negative integer and an integer k.

We must remove exactly k digits from num.

After removing those digits, the remaining digits must stay in their original relative order.

Return the smallest possible integer as a string.

The result should not contain leading zeroes. If all digits are removed, or the remaining number becomes empty after removing leading zeroes, return "0".

Input and Output

Example function shape:

def removeKdigits(num: str, k: int) -> str:
    ...

Examples

For:

num = "1432219"
k = 3

The answer is:

"1219"

We remove 4, 3, and one 2.

The remaining digits form the smallest possible number:

1 2 1 9

Another example:

num = "10200"
k = 1

The best digit to remove is 1.

That leaves:

"0200"

After removing leading zeroes, the result is:

"200"

Another example:

num = "10"
k = 2

We remove both digits.

Nothing remains, so the answer is:

"0"

First Thought: Brute Force

A brute force solution would try every way to remove k digits.

For each candidate result, we compare it with the best answer found so far.

This works for tiny inputs, but the number of ways to remove digits is large.

If num has length n, the number of possible choices is:

C(n, k)

That becomes too large when n is up to 100000.

We need a linear greedy method.

Key Insight

For numbers with the same length, the leftmost digits matter the most.

For example:

1299 < 1399

because the second digit 2 is smaller than 3.

So when we scan from left to right, if we see a smaller digit after a larger digit, we should remove the larger digit if we still can.

Example:

num = "143..."

When we see 3, the previous digit is 4.

Keeping 3 before the rest gives a smaller prefix than keeping 4.

So we should remove 4.

This suggests a monotonic stack.

We build the answer from left to right. While the last kept digit is larger than the current digit, we remove the last kept digit.

Algorithm

Use a stack to store the digits we keep.

For each digit d in num:

1. While the stack is not empty, k > 0, and the top digit is greater than d, pop the stack.
2. Push d into the stack.
3. After processing all digits, if removals remain, remove digits from the end.
4. Join the stack into a string.
5. Remove leading zeroes.
6. Return "0" if the result is empty.

Correctness

The algorithm removes a previous digit only when three conditions hold:

k > 0
stack[-1] > current_digit

and the stack is non-empty.

This means a larger digit appears before a smaller digit. Removing the larger digit lets the smaller digit move into a more significant position. That strictly improves the number’s prefix.

The stack therefore keeps the smallest possible prefix after each processed digit, given the number of removals used so far.

If the input is already increasing, such as:

"123456"

then no earlier digit is larger than a later digit. In that case, removing from the end is optimal because earlier digits are more significant and smaller.

After exactly k removals, the stack contains the best possible ordered subsequence of digits. Removing leading zeroes only changes the string representation, not the numeric value.

Therefore, the algorithm returns the smallest possible integer.

Complexity

Implementation

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []

        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1

            stack.append(digit)

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

        result = "".join(stack).lstrip("0")

        return result if result else "0"

Code Explanation

We start with an empty stack:

stack = []

This stack stores the digits we currently plan to keep.

Then we scan each digit:

for digit in num:

The main greedy step is:

while k > 0 and stack and stack[-1] > digit:
    stack.pop()
    k -= 1

If the previous kept digit is larger than the current digit, removing it makes the number smaller. We can keep doing this while we still have removals left.

Then we keep the current digit:

stack.append(digit)

After the scan, we may still have removals left. This happens when the digits are already increasing.

For example:

num = "12345"
k = 2

The best result is:

"123"

So we remove from the end:

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

Then we build the result:

result = "".join(stack).lstrip("0")

Finally:

return result if result else "0"

This handles cases like "10" with k = 2, or "10200" with k = 1.

Testing

def test_remove_k_digits():
    s = Solution()

    assert s.removeKdigits("1432219", 3) == "1219"
    assert s.removeKdigits("10200", 1) == "200"
    assert s.removeKdigits("10", 2) == "0"
    assert s.removeKdigits("123456", 3) == "123"
    assert s.removeKdigits("100200", 1) == "200"
    assert s.removeKdigits("9", 1) == "0"
    assert s.removeKdigits("112", 1) == "11"

    print("all tests passed")

Test Notes