Remove K Digits

Q: What is the time complexity of Remove K Digits?

With a monotonic stack it runs in O(n) time for n digits: each digit is pushed once, and each pop spends one of the k removals. The stack holds up to n digits, so the extra space is O(n) . Rescanning from the left for each removal costs O(n·k) .

MediumMonotonic stack Greedy

+10

You get a non-negative number written as a string of digits, num, and an integer k. Remove exactly k digits and keep the rest in their original order, so that the number left is as small as possible.

Return it as a string without leading zeros. If nothing is left, or only zeros, return "0".

Function

removeKdigits(num: string, k: integer) → string

numstring: the number, written as a string of digits
kinteger: how many digits to remove
Returnsstring: the smallest number you can leave, as a string without leading zeros

Constraints

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num holds only the digits 0 to 9.
num has no leading zeros, except when it is the number zero itself, "0".

Examples

Input: num = "4325043"k = 3
Output: "2043"
Explanation: Dropping the 4 and the first 3 puts the 2 in front. The 0 cannot lead: four digits stand before it and you have three removals. The last removal takes the 5, which sits before a smaller 0.

Input: num = "30200"k = 1
Output: "200"
Explanation: Dropping the 3 leaves 0200, and without its leading zero that is 200. Any other removal keeps the 3 in front and leaves a four-digit number such as 3000.

Input: num = "52"k = 2
Output: "0"
Explanation: Both digits are removed, so nothing is left and the answer is "0".

Follow-up

How would you change the solution to remove k digits and leave the largest number instead?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The leftmost digits weigh the most, so the first digit that is bigger than its right neighbor should go. A stack of the digits you keep applies that rule to the whole string in one pass. Removals left over at the end come off the back, and leading zeros are stripped last.

Remove one digit at a time

Correct, but does not finish on the largest tests

Intuition

Remove one digit at a time: find the first position i where num[i] > num[i+1] and delete num[i], or delete the last digit if the digits never go down. Repeat k times.

Every answer keeps n-k digits, so the first position where two answers differ decides which is smaller. Up to i the digits never go down, so deleting an earlier digit slides in one at least as big; deleting a later one leaves the big num[i] in place. Deleting num[i] lowers the earliest position that can be lowered.

Each removal rescans from the left and shifts the digits after it, so the work is O(n·k). On 40,000 ones with k = 25,000, the scans read about 6.9 × 10^8 digits.

Algorithm

Copy the digits into a list you can delete from.
Repeat k times: walk from the left to the first digit bigger than the next one, or to the last digit, and delete it.
Strip the leading zeros, and return "0" if nothing remains.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

Monotonic stack of kept digits

Intuition

After the slow version deletes num[i], the digits before i still never go down, so the next drop can only start at the digit before the gap. A stack holds that prefix: the kept digits, never decreasing from bottom to top. When a new digit is smaller than the top, the top is bigger than its right neighbor, the digit the slow version would delete. Pop it, spend a removal, and keep popping while the new top is still bigger.

On 4325043 with k = 3, the 3 pops the 4, the 2 pops the 3 and the 0 pops the 5. The 4 and the 3 are pushed as they come, giving 2043.

Each digit is pushed once and each pop spends one of the k removals, so the pass is O(n).

Algorithm

Create an empty stack of digits.
For each digit of num: while removals are left and the top of the stack is bigger than the digit, pop the top and use up one removal. Then push the digit.
If removals are left after the loop, remove that many digits from the top of the stack.
Read the stack from bottom to top, skip the leading zeros, and return the rest, or "0" if nothing is left.

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

Pitfalls and edge cases

Popping when the top equals the new digit. In 112 with k = 1, that leaves 12; the right answer is 11.
Forgetting the removals left after the loop, or taking them from the front. The stack never decreases, so its last digits go: 123456789 with k = 3 gives 123456.
Counting stripped zeros as removals. In 100200 with k = 1, the 1 is the only removal; the zeros in front go for free, and the answer is 200.
Returning an empty string. 10 with k = 1 leaves only a zero, so the answer is "0".
Turning num into an integer. It can have 4 × 10^4 digits, far past any integer type, so compare the digits as characters.

Frequently asked questions3

What is the time complexity of Remove K Digits?

With a monotonic stack it runs in O(n) time for n digits: each digit is pushed once, and each pop spends one of the k removals. The stack holds up to n digits, so the extra space is O(n). Rescanning from the left for each removal costs O(n·k).

How do you handle leading zeros in Remove K Digits?

Remove the digits first and strip the zeros only at the end. A zero in front does not change the value, so it costs no removal: 10200 with k = 1 becomes 0200 and then 200. If the stripping leaves nothing, return "0".

Can Remove K Digits be solved with O(1) extra space?

Yes, if you may change the input. The stack never holds more digits than you have read, so it can live in the front of the digit array itself, with one index for its top. Languages with immutable strings still need one copy of the digits, which is O(n).

def removeKdigits(num, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

num = "4325043"
k = 3

Expected Output

"2043"