LESSON 336 OF 442 · STACK

Remove K Digits in Scala: A Greedy Stack in Linear Time

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 20

Guided

Ctrl + Enter to check

SCALA · STACK

Remove K Digits in Scala, explained

Problem overview

The method removeKdigits receives num, a string of digits that stands for a non-negative number, and an integer k. It must delete exactly k digits, keep the rest in their original order, and return the smallest number that can result, as a string without leading zeros. If nothing is left, or only zeros, the answer is "0".

With "1432219" and k = 3, removing the 4, the 3 and one of the 2s leaves "1219". With "10200" and k = 1, removing the 1 leaves "0200", which is written as "200". With "10" and k = 2 every digit goes, and the answer is "0". Since num can have 100,000 digits, the answer has to be built string-wise: it is not a number that fits into an Int or even a Long.

Approach: drop a digit when a smaller one follows

All results have the same length (num.length - k digits, before zeros are trimmed), so the smaller number is the one that is smaller at the first position where two candidates differ. That suggests a greedy rule: the leftmost digits matter most.

Look at two neighbours, a bigger digit followed by a smaller one, such as 4 then 3. If one of them has to go, removing the bigger one is better: the smaller digit moves into its place, and the number gets smaller at that position. Removing anything later could not do as well, since earlier positions weigh more.

So read the digits from left to right and keep the digits chosen so far on a stack. Before pushing a new digit c, pop every digit on top that is larger than c, as long as removals remain. After that the stack never decreases from bottom to top, except where the removal budget ran out.

If the digits only grow, as in 1234, nothing is popped and some removals are left over. The stack is then ascending, so its largest digits are at the top. Dropping from the top is the best use of the leftover removals.

Last, the stack may start with zeros, as in 0, 2, 0, 0 for "10200". Leading zeros are skipped when the string is written, and an empty result becomes "0".

Here is "1432219" with k = 3. The stack goes 1, then 1 4. The digit 3 pops the 4 (two removals left): 1 3. The next 2 pops the 3 (one left): 1 2. The second 2 isn't smaller than the top, so it is pushed: 1 2 2. The 1 pops one 2 and uses the last removal: 1 2 1. With no removals left, 9 is pushed, giving 1 2 1 9.

Step by step

Copy k into var remaining. Parameters in Scala can't be reassigned, and the count has to go down with every removal.
Create the stack as an empty ArrayBuffer[Char] in a val. Its end is the top. A buffer keeps the digits in the order they will be written, which a mutable.Stack (it hands back its elements top first) would not.
Loop over the digits with for (c <- num). A String can be traversed as a sequence of Chars.
Pop while a bigger digit is on top. The inner loop runs while remaining > 0, the stack is not empty, and stack.last > c. stack.nonEmpty goes before stack.last, because last on an empty buffer throws. Digit characters compare like the digits they show.
Remove the top with stack.remove(stack.length - 1).
Count the removal with remaining -= 1. When it reaches 0, the loop condition fails.
Push the digit with stack.append(c). It may still be popped later by a smaller digit.
Use up leftover removals with a second loop, while (remaining > 0).
Drop the top again with remove(stack.length - 1). At this point the stack is non-decreasing, so the top is the biggest digit.
Count it with remaining -= 1.
Delegate the output by ending with a call to joinWithoutLeadingZeros(stack), whose value is the method's result.
Declare the helper as a private method that takes the buffer and returns a String.
Start with startingZeros = true. This flag says that only zeros have been seen so far.
Create a StringBuilder with new StringBuilder() to collect the output without copying the text for every digit.
Loop over the buffer with for (ch <- stack), from the bottom, which is the front of the number.
Test ch != '0'. The first digit other than zero ends the run of leading zeros.
Set startingZeros = false inside that test. The flag never goes back to true, so zeros inside the number, like the two in 200, are kept.
Test !startingZeros in a second if.
Append ch to result.
Finish with if (result.isEmpty) "0" else result.toString. In Scala an if is an expression, so it can be the method's last line.

The solution in Scala

class Solution {
    def removeKdigits(num: String, k: Int): String = {
        var remaining = k
        val stack = scala.collection.mutable.ArrayBuffer[Char]()
        for (c <- num) {
            while (remaining > 0 && stack.nonEmpty && stack.last > c) {
                stack.remove(stack.length - 1)
                remaining -= 1
            }
            stack.append(c)
        }
        while (remaining > 0) {
            stack.remove(stack.length - 1)
            remaining -= 1
        }
        joinWithoutLeadingZeros(stack)
    }

    private def joinWithoutLeadingZeros(stack: scala.collection.mutable.ArrayBuffer[Char]): String = {
        var startingZeros = true
        val result = new StringBuilder()
        for (ch <- stack) {
            if (ch != '0') {
                startingZeros = false
            }
            if (!startingZeros) {
                result.append(ch)
            }
        }
        if (result.isEmpty) "0" else result.toString
    }
}

The Scala details worth a closer look:

Comparing Chars. stack.last > c compares character codes. The codes of '0' to '9' are consecutive and in order, so a character comparison gives the same answer as comparing the digits.
remove takes an index. On an ArrayBuffer, remove(i) deletes the element at position i and returns it. With the last index it is a constant-time pop. The result is ignored here.
last on an empty buffer throws NoSuchElementException. The nonEmpty test in front of it, joined with &&, stops the evaluation before last runs.
Reading for (c <- num). It runs the body once for each character, in order. It is a loop, not a collection builder, because there is no yield.
private def. The helper is visible only inside the class. Its parameter type is written with the full package name, matching how the buffer is created in removeKdigits.
The if expression. if (result.isEmpty) "0" else result.toString has the value of whichever branch runs, and both branches are Strings. toString can be written without parentheses.

Complexity

Let n be the length of num.

Time: O(n). Each digit is pushed once and popped at most once, so the two loops together do at most about 2n stack operations. The helper walks the stack once.

Space: O(n). The stack can hold all the digits, and the StringBuilder holds up to as many.

Edge cases and common mistakes

Removing everything. With "10" and k = 2 the stack ends up empty and the method returns "0". The same holds for "12345" with k = 5.
Only zeros left. "100" with k = 1 leaves the digits 0, 0. Every zero is a leading zero, so the builder stays empty and the result is "0". "10001" with k = 4 also gives "0".
Ascending digits. "1234" with k = 2 pops nothing in the main loop. The second loop drops 4 and 3, and the answer is "12". Without the second loop, the answer would be too long.
Equal neighbours. "112" with k = 1 gives "11". The comparison is strict (>), so a digit equal to the top is pushed and nothing is popped for it. Popping on equality would remove digits without making the number smaller.
Converting to a number. The input can be 100,000 digits long, far past Long. Keep everything as characters.
Trimming zeros too early. Removing the zeros while the stack is built would change which digits are compared. The stack keeps them. Only the output step skips the leading ones.
Checking last first. Writing stack.last > c && stack.nonEmpty throws on the very first digit, when the stack is empty.

Testing

"1432219", k = 3 gives "1219".
"10200", k = 1 gives "200".
"10", k = 2 gives "0".
"1234", k = 2 gives "12".
"112", k = 1 gives "11".
"5337", k = 2 gives "33".
"100", k = 1 gives "0".

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

Start learning free