LESSON 337 OF 443 · STACK

Remove K Digits in Swift: A Monotonic Stack of Characters

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

SWIFT · STACK

Remove K Digits in Swift, explained

Problem overview

The method removeKdigits receives a string num of digits and an integer k. It must delete exactly k digits, keeping the order of the rest, so that the number that remains is as small as possible. The answer is a string without leading zeros, and "0" if nothing is left.

For num = "1432219" and k = 3, removing 4, 3 and 2 leaves "1219". For "10200" with k = 1, removing the 1 leaves "0200", which is written "200" after the leading zero goes. For "10" with k = 2, every digit is removed and the answer is "0".

Approach: drop a digit that is bigger than the next one

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

That gives the rule. Scan the digits from left to right. When a digit is smaller than the digit before it, deleting the earlier, bigger one puts the smaller digit into its place, and the number gets smaller. So keep a stack of the digits you keep, and before pushing a new digit, pop every stack digit that is greater than it, as long as you still have removals left.

Trying every set of k digits to remove is exponential. The stack makes it linear: each digit is pushed once and popped at most once.

On "1432219" with k = 3: push 1, then push 4 (it is bigger than 1, nothing to pop). The 3 pops the 4 and is pushed, so the stack is 1, 3 and two removals remain. The 2 pops the 3 and is pushed: 1, 2, one removal left. The next 2 pops nothing, because the top is not greater than it: 1, 2, 2. The 1 pops one 2, which uses the last removal, and is pushed: 1, 2, 1. The 9 is pushed with no removals left, giving "1219".

If the scan finishes with removals left over, the digits never went down, for example "1234". The stack is then non-decreasing, so its largest digits are at the top, and the extra removals take digits off the end: "1234" with k = 2 gives "12".

Step by step

Copy k into a var called remaining. Swift function parameters are constants, so k itself can't be decremented.
Create the stack as an empty [Character]. The end of the array is the top: append pushes, last reads and removeLast() pops.
Loop over the characters of num with for c in num. Iterating a String gives Character values.
Pop bigger digits while there are removals left, the stack isn't empty, and the top is greater than c. Comparing digit characters orders them like the digits.
Pop the top with removeLast().
Count the removal by decreasing remaining.
Push c. It stays for now, and a later, smaller digit may pop it.
Use up leftover removals after the loop with a second while remaining > 0.
Pop from the top in that loop: the stack never decreases from bottom to top at this point, so the top is the largest digit.
Count each of these removals too.
Return the result of a helper, joinWithoutLeadingZeros, because the stack may start with zeros.
Declare the helper inside the class. Its parameter has no argument label (_), so it is called as joinWithoutLeadingZeros(stack).
Start with a flag startingZeros set to true: no digit other than 0 has been seen.
Create an empty string result.
Loop over the stack from bottom to top, which is the number's order.
Check for a nonzero digit: ch != "0". Swift writes a character literal with double quotes, like a string.
Clear the flag. Once cleared it stays cleared, so later zeros, as in 200, are kept.
Check !startingZeros. Zeros at the front are skipped; everything after them is kept.
Append the digit to result.
Return "0" for an empty result and result otherwise, using the ternary operator.

The solution in Swift

class Solution {
    func removeKdigits(_ num: String, _ k: Int) -> String {
        var remaining = k
        var stack: [Character] = []

        for c in num {
            while remaining > 0 && !stack.isEmpty && stack.last! > c {
                stack.removeLast()
                remaining -= 1
            }
            stack.append(c)
        }

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

        return joinWithoutLeadingZeros(stack)
    }

    func joinWithoutLeadingZeros(_ stack: [Character]) -> String {
        var startingZeros = true
        var result = ""

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

        return result.isEmpty ? "0" : result
    }
}

Swift details worth knowing:

Strings can't be indexed by integers. Writing num[0] doesn't compile: the compiler reports cannot subscript String with an Int, use a String.Index instead. Looping with for c in num avoids the problem, and Array(num) gives an indexable array of characters when you need one.
Character comparison. stack.last! > c compares two characters by their Unicode values. For the digits "0" to "9" that matches numeric order, which is why the lesson doesn't convert them to integers.
Optional last. stack.last is nil for an empty array. The condition checks !stack.isEmpty before force unwrapping, and && stops at the first false.
removeLast() on an empty array crashes. The final loop is safe because the constraints guarantee k is at most num.count, so there are always enough digits.
Building the string. result.append(ch) adds a Character to a String. The helper is an instance method, so inside removeKdigits you call it by its plain name.

Complexity

Time: O(n), where n is the number of digits. Each digit is pushed once and popped at most once, and the helper makes one more pass over the stack.

Space: O(n). The stack can hold every digit, and the result string is built from it.

Edge cases and common mistakes

Removing everything. "10" with k = 2, and also "9" with k = 1, leave an empty stack. The helper returns "0".
Leading zeros. "10200" with k = 1 gives "200", not "0200". Only the zeros before the first nonzero digit go; the zeros in 200 stay.
Zeros only. "100" with k = 1 gives "0": the stack holds 0, 0, every digit is skipped as a leading zero, and the empty result becomes "0".
Increasing digits. "1234" with k = 2 gives "12". Forgetting the second loop would return the whole string.
Equal digits. "112" with k = 1 gives "11". The comparison is strict, so equal digits don't pop each other.
Decreasing digits. "4321" with k = 2 gives "21": each new digit pops the one before it until the removals are used.
Converting to an integer. The input can have up to 100,000 digits, far more than an Int holds, so the number must stay a string.

Testing

("1432219", 3) gives "1219".
("10200", 1) gives "200".
("10", 2) gives "0".
("1234", 2) gives "12", and ("4321", 2) gives "21".
("1173", 2) gives "11", and ("5337", 2) gives "33".

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

Start learning free