Remove K Digits

Monotonic non-decreasing stack, greedy from the left

time O(n)space O(n)

Trying every set of k removals is exponential, but position beats value here: the leading digit is worth ten times the next one, so the very first place where a digit is followed by something smaller is always the best place to cut. Sweeping left to right with a stack turns that into one pass — before pushing a digit, pop every larger digit still on top while removals remain, because each pop shrinks an earlier and therefore heavier position. What survives is a non-decreasing run, which is the smallest arrangement reachable. Two loose ends the loop does not cover: if the digits ran uphill the whole way no pop ever fired, so the leftover removals come off the tail where they cost least, and a stack that now starts with zeros needs them stripped, since a number is not written with leading zeros. Each index is pushed once and popped at most once, so the pass is linear.

Details

Animated on: num = "10432219", k = 3. Remove exactly 3 digits so the remaining number is as small as possible. Answer: "2219".

Problem:Remove K DigitsMedium

Monotonic non-decreasing stack, greedy from the left

step 1 / 10

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

num=10432219, k=3, so 8 - 3 = 5 digits survive. The leftmost digit weighs the most, so the number shrinks fastest by killing the earliest digit that is bigger than the one right after it. Sweep left to right keeping a stack of digits that never goes downhill.

Pseudocode

1FUNCTION removeKDigits(num, k):
2  stack <- EMPTY
3  FOR i <- 0 TO LENGTH(num) - 1:
4    WHILE stack NOT EMPTY AND k > 0 AND TOP(stack) > num[i]:
5      POP stack
6      k <- k - 1
7    PUSH num[i] ONTO stack
8  WHILE k > 0:
9    POP stack
10    k <- k - 1
11  STRIP LEADING ZEROS FROM stack
12  RETURN JOIN(stack)

← / → step · space play · Home restart

Every step in words

Show all 10 steps

num=10432219, k=3, so 8 - 3 = 5 digits survive. The leftmost digit weighs the most, so the number shrinks fastest by killing the earliest digit that is bigger than the one right after it. Sweep left to right keeping a stack of digits that never goes downhill.
Digit 1 at index 0. Push 1; kept so far 1.
Digit 0 at index 1. 1 sat to the left of the smaller 0, and a bigger digit in an earlier position costs more than anything it could save later — drop it, 2 removals left. Push 0; kept so far 0.
Digit 4 at index 2. 0 on top is already <= 4, so removing it would only make an earlier position bigger — keep it. Push 4; kept so far 04.
Digit 3 at index 3. 4 sat to the left of the smaller 3, and a bigger digit in an earlier position costs more than anything it could save later — drop it, 1 removal left. Push 3; kept so far 03.
Digit 2 at index 4. 3 sat to the left of the smaller 2, and a bigger digit in an earlier position costs more than anything it could save later — drop it, 0 removals left. Push 2; kept so far 02.
Digit 2 at index 5. All 3 removals are spent, so nothing can be popped any more. Push 2; kept so far 022.
Digit 1 at index 6. All 3 removals are spent, so nothing can be popped any more. Push 1; kept so far 0221.
Digit 9 at index 7. All 3 removals are spent, so nothing can be popped any more. Push 9; kept so far 02219.
The stack reads 02219, but 1 leading zero is not part of a number's spelling, so strip it: the answer is 2219.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Remove K Digits in the editor All Stack problems Back to roadmap