Stack • Greedy Algorithms

Remove K Digits

Given a string representing a non-negative integer, remove exactly K digits to form the smallest possible integer.

The Greedy Choice

In the number `432`, removing `4` yields `32`, but removing `2` yields `43`. You always want smaller digits at the most significant (leftmost) positions.

Monotonic Stack

We use a stack to build our answer. If the current digit is smaller than the top of the stack, popping the top of the stack makes the overall number smaller!

Edge Cases

Watch out for leading zeros (don't push '0' into an empty stack) and cases where the digits are already in increasing order (like `1234`). In the latter, you must manually pop from the end until K is 0.

1432219

K (Removals Left)3

Stack (Resulting Digits)

Empty

Code Tracker

:::

1let stack = [];

2for (let char of num) {

3 while (k > 0 && stack.length > 0 && stack[stack.length - 1] > char) {

4 stack.pop();

5 k--;

6 }

7 if (stack.length > 0 || char !== '0') {

8 stack.push(char);

9 }

10}

11while (k > 0 && stack.length > 0) {

12 stack.pop();

13 k--;

14}

15return stack.length === 0 ? '0' : stack.join('');