402.remove-k-digits.md

402. Remove K Digits

Monotonic Stack

Given sequence of digits, how can we build the smallest number? Suppose we have digits = [1, 3, 2], then the smallest number would be 123 which is the digits in ascending order.

To create the smallest number, we try to find the smaller digit as possible. To find the next smaller digit, we can use monotonic stack while ensuring that the digits in the stack are ascending order.

fun removeKdigits(num: String, k: Int): String {
    val stack = LinkedList<Char>()
    var remainingK = k
    // We maintain the increasing monotonic stack
    for (c in num) {
        val n = c - '0'
        while (remainingK > 0 && stack.isNotEmpty() && (stack.peekLast() > n) {
            stack.removeLast()
            remainingK--
        }
        stack.addLast(n)
    }
    // If we still have remaining K, we remove the last K digits
    while (remainingK > 0 && stack.isNotEmpty()) {
        stack.removeLast()
        remainingK--
    }
    // Remove leading zeros
    while (stack.isNotEmpty() && stack.peekFirst() == '0') {
        stack.removeFirst()
    }
    // We have to check if the stack is empty, if it is, we return "0"
    return if (stack.isEmpty()) "0" else stack.joinToString("")
}

• Time Complexity: O(n)
• Space Complexity: O(n)