Remove K Digits Visualizer & Step-by-Step Algorithm Solution

Remove k digits from a number string using a greedy monotonic increasing stack to form the smallest possible integer.

Category: stack | Difficulty: Medium

Tags: Stack, Greedy, Monotonic Stack, String

Remove K Digits

Input Digits (num)
1
0
4
1
3
2
2
3
2
4
1
5
9
6
Push / Pop (Top)
(Empty Stack)
Monotonic Stack
100%
state
num1432219
k3
removals0
target removals3
Initialization
1/41
Explanation

Call removeKdigits(num = "1432219", k = 3). Objective: remove 3 digits to create the smallest possible number.

Source Code
1function removeKdigits(num: string, k: number): string {
2 const stack: string[] = [];
3 let removals = 0;
4 for (let n of num.split("")) {
5 const number = Number(n);
6 while (
7 removals < k &&
8 stack.length &&
9 Number(stack[stack.length - 1]) > number
10 ) {
11 removals++;
12 stack.pop();
13 }
14 stack.push(String(number));
15 }
16
17 while (removals < k) {
18 stack.pop();
19 removals++;
20 }
21
22 let i = 0;
23 while (i < stack.length - 1 && stack[i] === "0") i++;
24 const result = stack.slice(i).join("");
25 return result === "" ? "0" : result;
26}