LESSON 336 OF 442 · STACK

Remove K Digits in Go: Greedy Stack of Runes

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 19

Guided

Ctrl + Enter to check

Remove K Digits in Go, explained

Problem overview

The function removeKdigits receives a string num of digits, representing a non-negative integer, and a count k. It must delete exactly k digits so that the remaining digits, in their original order, form the smallest possible number, and return that number as a string. The result never has leading zeros, and if nothing is left it is "0". Here 1 <= k <= len(num) <= 100,000.

For "1432219" with k = 3, deleting 4, 3 and 2 leaves "1219". For "10200" with k = 1, deleting the 1 leaves "0200", which is written "200". For "10" with k = 2, everything is deleted and the answer is "0".

Approach: drop a digit when a smaller one follows it

Trying every way to choose which k digits to remove is exponential. A greedy rule is enough. All results have the same length, so the one that is smaller at the earliest differing position wins. That means the leftmost digits matter most.

Look at two neighbours where the left digit is bigger, such as 4 followed by 3. Removing the 4 puts the 3 in the 4's place, and the number gets smaller. So whenever a digit is bigger than the digit right after it, removing it is an improvement, and it is the most valuable one to make early.

A stack does this in one pass. Read the digits left to right. Before pushing a digit, pop every digit on top of the stack that is bigger than it, as long as removals remain. Every digit is pushed once and popped at most once, so the scan is linear.

If the scan ends with removals left over, no digit was ever followed by a smaller one, as in "1234". The stack is then in non-decreasing order, so its biggest digits are at the top, and removing from the top is best. Last, zeros at the front are dropped, and an empty result becomes "0".

Step by step

Create an empty stack of runes. It holds the digits kept so far, with the most recent on top.
Loop over the digits of num. Ranging over a string gives its characters as runes, so each c is a rune.
Add an inner loop that runs while removals remain (k > 0), the stack is not empty, and the top digit is greater than c. Digit characters compare in the same order as the digits they show.
Pop the top digit by re-slicing the stack without its last element.
Decrease k, since a removal was used.
Push c. It stays for now and may be popped by a smaller digit later.
After the loop, a second loop runs while k > 0, to spend the removals the first loop did not need.
Pop the top digit in that loop. The stack never decreases from bottom to top at this point, so the top is the biggest digit.
Decrease k again.
Return the result of a helper, joinWithoutLeadingZeros, called with the stack.
Declare the helper, taking a []rune and returning a string.
Create a flag startingZeros, set to true, and an empty result slice of runes.
Loop over the stack from bottom to top, which is the order of the digits in the number.
Check that the digit is not '0', and inside that check set the flag to false. The first non-zero digit ends the zeros at the front, and the flag never turns back to true, so later zeros, as in 200, are kept.
Check that the flag is false (!startingZeros) and, inside that check, append the digit to result. Zeros at the front are skipped; every digit after them is kept.
Handle the empty case: if result has no digits, return "0". Otherwise return string(result).

The solution in Go

func removeKdigits(num string, k int) string {
    stack := []rune{}

    for _, c := range num {
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > c {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, c)
    }

    for k > 0 {
        stack = stack[:len(stack)-1]
        k--
    }

    return joinWithoutLeadingZeros(stack)
}

func joinWithoutLeadingZeros(stack []rune) string {
    startingZeros := true
    result := []rune{}

    for _, ch := range stack {
        if ch != '0' {
            startingZeros = false
        }
        if !startingZeros {
            result = append(result, ch)
        }
    }

    if len(result) == 0 {
        return "0"
    }
    return string(result)
}

Go details worth a closer look:

Runes, not bytes. for _, c := range num yields runes, and the stack is a []rune. Digits are single bytes in UTF-8, so indexing with num[i] would work too, but it gives byte values, a different type from the stack's elements.
Comparing digit characters. A rune is a number: '9' > '1' is true because their codes, 57 and 49, are in the same order as the digits. No conversion to an integer is needed.
Popping. stack = stack[:len(stack)-1] makes the slice one element shorter without copying anything. The old element stays in the backing array until it is overwritten, which is harmless here.
k is a copy. The function receives k by value, so decrementing it changes only the local variable.
Back to a string. string(result) converts a []rune into a string. Appending to a rune slice is cheap, whereas building a string by repeated + would copy the text each time.
Safe final popping. The second loop pops k times from a stack that holds at least k digits, because k <= len(num) and every digit pushed and not popped is still on it.

Complexity

Time: O(n), where n is the length of num. Each digit is pushed once and popped at most once, in either the first or the second loop. The helper makes one more pass over the stack.

Space: O(n). The stack and the result slice each hold at most n runes.

Edge cases and common mistakes

Removing every digit. "10" with k = 2 leaves an empty stack, and the helper's final check turns that into "0".
Leading zeros. "10200" with k = 1 leaves 0, 2, 0, 0 on the stack. The helper skips only the zero at the front, so the answer is "200" and not "20".
Only zeros remain. "100" with k = 1 gives the stack 0, 0. Every zero is skipped, and the answer is "0".
Increasing digits. "1234" with k = 2 pops nothing in the main loop. The second loop removes the last two digits and the answer is "12". Without that loop, the result would keep too many digits.
Equal digits. "112" with k = 1 pops nothing, because the comparison is strict, and the final loop removes the 2: the result is "11". Using >= would pop equal digits for no gain.
Decreasing digits. For "54321" with k = 2 each new digit pops the previous one until the removals run out, leaving "321".
Converting to an integer. The number can have 100,000 digits, so it must stay a string. It does not fit in any integer type.

Testing

"1432219" with k = 3 gives "1219".
"10200" with k = 1 gives "200".
"10" with k = 2 gives "0".
"1234" with k = 2 gives "12".
"9" with k = 1 gives "0".
"1111" with k = 4 gives "0".

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

Start learning free