Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Remove K Digits
• Topics: String, Stack, Greedy, Monotonic Stack

Problem gist

The problem gives a non-negative integer as a string and asks for the smallest possible number after removing exactly k digits. The answer must not keep unnecessary leading zeroes, and if every digit is removed or the remaining digits are all zeroes, the answer is "0".

The key detail is that the relative order of the digits that remain cannot change. This turns the task into choosing the best subsequence of length len(num) - k.

How to derive the greedy solution

To make the final number as small as possible, the earliest digits matter the most. Whenever a bigger digit appears before a smaller digit, removing the bigger earlier digit is usually better than spending a deletion later. For example, in 1432219, once the scan sees 3 after 4, deleting 4 immediately improves the most significant part of the answer.

That observation leads to a monotonic increasing stack. Scan digits from left to right. Before pushing the current digit, pop from the stack while the previous kept digit is larger than the current digit and deletions remain. Each pop removes a digit that would make the prefix larger than necessary.

If the scan finishes and deletions remain, the digits are already nondecreasing, so removing from the end is best. Trailing digits are the least significant among the remaining choices, and in a nondecreasing sequence they are also the largest available suffix digits.

Finally, strip leading zeroes from the built string. If nothing remains after stripping, return "0".

Python solution

from typing import List


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

        for digit in num:
            # If a smaller digit can move left by deleting the previous larger
            # digit, spend one deletion now because earlier positions dominate.
            while (
                digits_to_remove > 0
                and kept_digits
                and kept_digits[-1] > digit
            ):
                kept_digits.pop()
                digits_to_remove -= 1

            kept_digits.append(digit)

        # If the number was already increasing, remove the largest suffix digits.
        if digits_to_remove > 0:
            kept_digits = kept_digits[:-digits_to_remove]

        smallest_number = "".join(kept_digits).lstrip("0")
        return smallest_number or "0"

The algorithm visits each digit once and each digit can be popped at most once, so the time complexity is O(n). The stack stores up to n digits, so the space complexity is O(n).

Common mistakes

A tempting but incorrect approach is to repeatedly remove the largest digit. Position matters more than raw digit value: removing a large digit near the end may do far less than removing a slightly smaller digit near the front.

Another common bug is forgetting the leftover-deletion case. Inputs like 123456 never trigger a stack pop, but exactly k digits still need to be removed, so the correct move is to trim the suffix.

Leading zeroes also need deliberate handling. For 10200 with k = 1, the greedy stack builds 0200, but the returned number should be 200.

Interview follow-ups

What if the interviewer asks for the largest possible number after removing k digits?

The same stack pattern works with the comparison reversed. Instead of popping while the previous kept digit is greater than the current digit, pop while it is smaller. That lets larger digits move left into more significant positions.

If deletions remain after the scan, remove from the end for the same reason as the original problem: once the kept digits are monotonic in the desired direction, the least valuable remaining positions are at the suffix. The time and space complexity remain O(n).

What if the input is a stream and the full string is too large to keep?

The monotonic stack is still the right conceptual tool, but the implementation must be careful about output timing. A digit can only be safely emitted once it can no longer be removed. If there are r deletions remaining, the last r kept digits are still at risk because a future smaller digit could cause them to be popped.

The practical approach is to keep a deque or stack buffer and flush only the prefix that is guaranteed stable. This preserves the greedy behavior while bounding retained data when k is much smaller than the stream length. In the worst case, such as a long increasing stream, the algorithm may still need to retain many digits until it knows how to spend the remaining deletions.

What if exactly k removals changes to at most k removals?

For non-negative decimal strings, the optimal strategy still uses as many removals as allowed, up to the length of the string. Removing a digit cannot increase the integer value after leading zeroes are normalized: the result either has fewer significant digits or keeps a no-larger prefix.

That means the same greedy implementation works with k = min(k, len(num)). If every digit is removed, the normalized answer is "0". The complexity remains O(n) time and O(n) space.

What if the interviewer asks why the greedy pop is safe?

Suppose the stack ends with digit a, the current digit is smaller digit b, and a deletion is still available. Keeping a before b makes the first differing position larger than the alternative that deletes a and lets b move left. Since earlier digits dominate numeric order, deleting a cannot make the best possible answer worse.

This exchange argument applies every time the loop pops. Repeating it until the stack is empty, deletions are exhausted, or the previous digit is no longer larger creates the smallest prefix available at that point. Once a prefix digit survives this process, no earlier unseen digit exists that could replace it, so the local decisions compose into the global optimum.