LESSON 336 OF 442 · STACK

Remove K Digits in Kotlin: O(n) Greedy Solution with a Stack

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

KOTLIN · STACK

Remove K Digits in Kotlin, explained

Problem overview

The function removeKdigits receives num, a string of digits that represents a non-negative integer, and an integer k. It must delete exactly k digits, keeping the others in their original order, so that the number left is as small as possible. It returns that number as a string, without leading zeros. If nothing is left, or only zeros, the answer is "0".

For num = "1432219" and k = 3, removing 4, 3 and one 2 leaves "1219". For "10200" and k = 1, removing the 1 leaves "0200", which must be written "200". For "10" and k = 2, every digit goes, and the answer is "0".

The string can have up to 100,000 digits, so the answer can't be stored in an Int or a Long: converting a 100,000-digit string with toInt() throws a NumberFormatException. The work has to be done on the digits.

Approach: drop a digit when a smaller one follows

All results have the same length, num.length - k, so the smallest one is the one with the smallest first digit, then the smallest second digit, and so on. That points to a greedy rule.

Look at two neighbours where the left digit is bigger, such as 4 followed by 3. Removing the 4 puts the 3 in its place, and the number gets smaller at that position, whatever comes after. So whenever a digit is bigger than the digit that follows it, it is worth removing, if removals remain.

A stack does this in one pass. Read the digits left to right. Before pushing a digit c, pop every digit from the top that is bigger than c, as long as removals are left. Then push c. The stack always holds the best digits chosen so far, in order.

For "1432219" with k = 3 the stack changes like this:

after 1: 1      removals left: 3
after 4: 14     removals left: 3
after 3: 13     removals left: 2   (4 was popped)
after 2: 12     removals left: 1   (3 was popped)
after 2: 122    removals left: 1
after 1: 121    removals left: 0   (2 was popped)
after 9: 1219   removals left: 0

Two cleanups remain. If the digits never go down, as in "1234", nothing is popped and removals are left. The stack then increases from bottom to top, so the biggest digits are at the top, and dropping from the top is best. Finally, the stack may start with zeros, which must be skipped.

Step by step

Copy k into a var named remaining. Kotlin parameters are read-only, so k itself can't be decremented.
Create the stack as an empty ArrayDeque<Char>. Its end is the top: addLast pushes, last() reads the top and removeLast() pops it.
Loop over the digits of num with the variable c.
Write the popping loop. It runs while remaining > 0, the stack is not empty and stack.last() > c. Check isNotEmpty() before last(), because last() throws on an empty deque. The && operator stops at the first false condition, so the order matters.
Pop the top digit. It is bigger than c, and c takes its place.
Decrease remaining by one.
Push c. It stays for now, and a smaller digit later may pop it.
After the loop, spend the leftover removals with while (remaining > 0).
Pop the top digit inside it. The stack doesn't decrease from bottom to top at this point, so the top is its biggest digit.
Decrease remaining. The loop does exactly the removals that were left.
Return the helper's result. The stack may start with zeros: for "10200" and k = 1 it holds 0, 2, 0, 0. A helper called joinWithoutLeadingZeros turns it into a clean string.
Declare the private helper taking an ArrayDeque<Char> and returning a String.
Set startingZeros to true. No non-zero digit has been seen yet.
Create a StringBuilder named result.
Loop over stack with ch. A for loop over a deque goes from first to last, which is the order of the digits in the number.
If ch is not '0',
set startingZeros to false. It stays false afterwards, so zeros inside the number, like the two in 200, are kept.
If !startingZeros,
append ch to result.
Return "0" when result is empty, and result.toString() otherwise. This is the case when nothing but zeros was left.

The solution in Kotlin

class Solution {
    fun removeKdigits(num: String, k: Int): String {
        var remaining = k
        val stack = ArrayDeque<Char>()

        for (c in num) {
            while (remaining > 0 && stack.isNotEmpty() && stack.last() > c) {
                stack.removeLast()
                remaining--
            }
            stack.addLast(c)
        }

        while (remaining > 0) {
            stack.removeLast()
            remaining--
        }

        return joinWithoutLeadingZeros(stack)
    }

    private fun joinWithoutLeadingZeros(stack: ArrayDeque<Char>): String {
        var startingZeros = true
        val result = StringBuilder()

        for (ch in stack) {
            if (ch != '0') {
                startingZeros = false
            }
            if (!startingZeros) {
                result.append(ch)
            }
        }

        return if (result.isEmpty()) "0" else result.toString()
    }
}

The Kotlin details worth a closer look:

ArrayDeque is Kotlin's own. It is available without an import and works at both ends. addLast, removeLast and last() all act on the end, so the end behaves as the top of a stack.
Char comparison. stack.last() > c compares the character codes, and the codes of '0' to '9' run in the same order as the digits. No conversion to numbers is needed. Comparing '9' > '1' gives true.
Iterating a String. for (c in num) yields the characters one at a time.
remaining--. This is a statement that decrements the var. It is written on its own line here, so its value is not used.
private fun. The helper is only for Solution itself. Members of a class are public by default in Kotlin, so private keeps it out of the class's interface.
if is an expression. return if (result.isEmpty()) "0" else result.toString() returns whichever branch is chosen.
StringBuilder. append adds one character without copying the text built so far. A String is immutable, so building it with += in a loop would copy it each time.

Complexity

Let n be the length of num.

Time: O(n). Each digit is pushed once and popped at most once, in the main loop or in the cleanup loop. The helper reads the stack once.

Space: O(n). The stack and the builder each hold up to n characters.

Edge cases and common mistakes

Removing everything. k equal to num.length empties the stack, and the helper returns "0". For "9" with k = 1 the answer is "0".
Increasing digits. "1234" with k = 2 pops nothing in the main loop, and the cleanup loop removes 4 and 3, leaving "12". Without that loop, the function would return all four digits.
Equal digits. "112" with k = 1 gives "11". The pop condition is strictly greater, so equal digits stay, and the 2 is removed in the cleanup loop.
Leading zeros. "100" with k = 1 leaves "00", and the answer is "0". The flag skips all the zeros at the front and keeps a lone "0" only through the empty-result rule.
Zeros inside. "10200" becomes "200" and not "2": only zeros before the first non-zero digit are dropped.
Decreasing digits. "54321" with k = 2 gives "321". The main loop pops 5 and 4 as the smaller digits arrive.
Converting to a number. Parsing the string, subtracting and printing fails for long inputs. Keep the digits as characters.
Calling last() on an empty deque. It throws an exception, which is why isNotEmpty() comes first in the condition.

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".
num = "10001", k = 4 gives "0".

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

Start learning free