LESSON 336 OF 442 · STACK

Remove K Digits in TypeScript: Greedy Monotonic Stack in O(n)

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

1 <= k <= num.length <= 10⁵
num consists of only digits.
num does not have any leading zeros except for the zero itself.

STEP 1 OF 18

Guided

Ctrl + Enter to check

TYPESCRIPT · STACK

Remove K Digits in TypeScript, explained

Problem overview

The method removeKdigits receives num, a string of digits that stands for a non-negative integer, and a number k. It must delete exactly k digits from num so that the number that remains is as small as possible, and return it as a string. The result has no leading zeros, and if nothing is left, or only zeros, the result is "0".

For "1432219" with k = 3, deleting the digits 4, 3 and 2 leaves "1219". For "10200" with k = 1, deleting the leading 1 leaves "0200", which is written "200". For "10" with k = 2, every digit goes and the answer is "0". The string can be up to 100,000 characters long, so the method needs to be linear.

Approach: drop a digit when a smaller one follows it

All the results have the same length, num.length - k digits, so the smallest number is the one that is smaller at the first position where they differ. The leftmost digits matter most.

That gives the greedy rule. Look at two neighbouring digits where the left one is bigger, such as the 4 in "1432...", followed by 3. Removing the bigger digit slides the smaller one into its place, which makes the number smaller. So whenever a digit is greater than the digit after it, it is a good one to remove, and the leftmost such digit is the best.

A stack applies the rule in one pass. Read the digits left to right and keep the digits you have decided to keep, with the most recent on top. For each new digit c:

While you still have removals left and the top of the stack is greater than c, pop it and use up one removal.
Then push c.

The stack ends up never decreasing from bottom to top, since a bigger digit above a smaller one would have been popped. Each digit is pushed once and popped at most once, so the pass is linear.

Two leftovers need handling after the pass. If removals remain, as in "1234" where no digit is ever bigger than its successor, the digits at the top are the biggest, so pop that many. And the stack may begin with zeros, which must be dropped from the written number.

On "1432219" with k = 3: push 1, push 4. The 3 is smaller than 4, so pop 4 (k = 2) and push 3. The 2 pops the 3 (k = 1) and is pushed. The next 2 doesn't pop anything, because 2 is not greater than 2, so it is pushed. The 1 pops one 2 (k = 0) and is pushed. The 9 is pushed. The stack is 1, 2, 1, 9, giving "1219".

Step by step

Create stack as an empty string[]. An array works as a stack, with push and pop at the end.
Loop over the digits of num with for...of, naming each one c.
Write the popping condition: k > 0, the stack is not empty, and its top is greater than c.
Pop the top digit. It is bigger than c, which takes its place.
Decrease k. When it reaches 0, the condition fails and nothing more is removed.
Push c after the popping loop. It stays for now, and a later smaller digit may remove it.
Spend leftover removals with a second loop that runs while k > 0.
Pop from the top in that loop, since the top holds the biggest digits.
Decrease k in the same loop.
Return the result of a helper, this.joinWithoutLeadingZeros(stack).
Declare the helper inside the class, taking a string[] and returning a string.
Set up a flag startingZeros, initially true, and an empty result.
Loop over the stack from bottom to top, which is the order of the digits in the number.
Check for a non-zero digit with ch !== '0'.
Turn the flag off at the first such digit. After that, later zeros are kept.
Test !startingZeros, meaning we are past the leading zeros.
Append ch to result.
Return "0" for an empty result, and result otherwise, in one ternary expression.

The solution in TypeScript

class Solution {
    removeKdigits(num: string, k: number): string {
        let stack: string[] = [];

        for (let c of num) {
            while (k > 0 && stack.length > 0 && stack[stack.length - 1] > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        while (k > 0) {
            stack.pop();
            k--;
        }

        return this.joinWithoutLeadingZeros(stack);
    }

    joinWithoutLeadingZeros(stack: string[]): string {
        let startingZeros = true;
        let result = "";

        for (let ch of stack) {
            if (ch !== '0') {
                startingZeros = false;
            }
            if (!startingZeros) {
                result += ch;
            }
        }

        return result === "" ? "0" : result;
    }
}

The TypeScript details that matter here:

String comparison works for single digits. > on two strings compares them character by character. For one-character strings that is the same as comparing the digits, since '0' to '9' are in increasing order. "9" > "1" is true. The trap is with longer strings: "9" > "10" is also true, because only the first characters are compared. The code avoids this because it compares one character at a time and never whole numbers.
for...of over a string yields its characters one by one, so c is a one-character string.
k is a parameter you can change. k-- modifies the local copy only, and the caller's value is untouched, since numbers are passed by value.
Arrays as stacks. pop() removes and returns the last element, and on an empty array it returns undefined without throwing. The constraint k <= num.length guarantees that the stack always has enough digits for the second loop anyway.
Why the helper builds a string. The result can be 100,000 digits long, far beyond what a number can hold exactly, since integers lose precision above 2^53. Keeping the answer as a string avoids any conversion.
this. in a method. The helper is called with this.joinWithoutLeadingZeros, because it belongs to the class instance.

Complexity

Time: O(n), where n = num.length. Every digit is pushed once and popped at most once, so the two loops over the digits and the stack take at most about 2n operations, and the helper makes one more pass.

Space: O(n). The stack holds up to n digits, and the result string is as long as what is left.

Edge cases and common mistakes

Removing everything. "10" with k = 2 pops everything. The helper's result is empty, so the method returns "0".
Increasing digits. "1234" with k = 2 pops nothing in the first loop. The second loop removes 4 and 3, leaving "12".
Equal digits. "112" with k = 1 gives "11". Equal neighbours are never popped, because the condition is a strict >, and the leftover removal takes the 2 from the top.
Leading zeros. "100" with k = 1 pops the 1 when the first 0 arrives, the stack becomes 0, 0, and the helper skips both zeros, giving "0". Zeros after the first non-zero digit stay, as in "200".
Forgetting the leftover removals. Without the second loop, "9" with k = 1 would return "9" instead of "0".
Converting to a number. Calling Number(num) or parseInt to strip zeros fails for long inputs, which lose precision, and the digits would come out as an exponent such as 1e+21.
Using >=. Popping equal digits would waste removals that the greedy rule says are not helpful at that position.

Testing

num = "1432219", k = 3 gives "1219".
num = "10200", k = 1 gives "200".
num = "10", k = 2 gives "0".
num = "1234", k = 2 gives "12".
num = "54321", k = 2 gives "321".

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free