Free Stacks and queues lessonsStacks and queues · Stage 2 · Monotonic stack · Step 4

The smallest number after removing digits

Remove exactly k digits from a number to make it as small as possible, by dropping any digit that is larger than the digit that follows it. About 18 minutes.

Drop the digit before a smaller one

In 1432219, removing 4 gives 132219, and removing 3 from that gives 12219. Each time you removed a digit that was bigger than the digit right after it. The digit that took its place was smaller, and the front of the number got smaller.

Keep a stack of the digits you keep. When a new digit is smaller than the top and you still have removals left, pop the top and use up a removal.

Smaller digit arrives: pop bigger digits while removals remain.

Push the digit: after the pops.

In code

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

Remove 3 digits from 1 4 3 2 2 1 9.

3 is smaller than 4, so remove 4. Removals left: 2. Stack: 1, 3.

Move 1 of 5

Tidy the ends

If the digits only ever rise, such as 12345, nothing gets popped and removals are left over. The best choice is to remove from the end, where the digits are biggest, so cut the last k digits off the stack.

Then remove leading zeros, because 0200 means 200. If no digits remain, the answer is the single digit 0.

Removals left over: cut them from the end.

Leading zeros: are removed; an empty result becomes 0.

In code

if k:
    stack = stack[:-k]
res = "".join(stack).lstrip("0")
return res or "0"

Quick check

Remove 1 digit from 12345. Which digit is removed?

A5, the last digit
B1, the first digit
C2

Show the answer

5, the last digit. The digits only rise, so nothing is ever popped. The leftover removal comes off the end.

Your problem

Remove k digits

You are given a string num representing a non-negative integer, and an integer k. Remove exactly k digits from num so that the new number is as small as possible, keeping the order of the remaining digits. Return it as a string without leading zeros. If nothing remains, return "0".

Example

num = "1432219", k = 3 → "1219"

1 ≤ length of num ≤ 100,000 · 0 ≤ k ≤ length of num · num has only digits and no leading zeros

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.