Remove K Digits - Leetcode Solution

Problem Statement:

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Example:

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 possible.

Solution:

The main idea here is to keep the digits that are smaller than their right neighbor. If there are no such digits, then we can simply remove the last digit, as the rightmost digit would be the largest. If k is not reduced to zero yet, we can repeat the same process again. However, in order to reduce the number of iterations, we can use a stack to keep track of the digits we have considered so far.

Algorithm:

1. Create an empty stack to keep track of the digits.
2. Loop through each digit in the num string.
   • While the stack is not empty and k > 0 and the top of the stack is greater than the current digit, pop the top element from the stack and decrease k.
   • Add the current digit to the stack.
3. If k is not zero, pop the top elements of the stack until k becomes zero.
4. If the stack is empty, return zero, otherwise return the digits in the stack as a string.

Python Code:

class Solution: def removeKdigits(self, num: str, k: int) -> str: digits = [] # create a stack to keep track of digits for digit in num: # while the stack is not empty, k is greater than 0, and the top of the stack is larger than the current digit while len(digits) > 0 and k > 0 and digits[-1] > digit: digits.pop() # remove the top element from the stack k -= 1 # decrease k digits.append(digit) # add the current digit to the stack

    # if k is still not zero, we need to remove the remaining digits from the end of the stack
    while k > 0 and len(digits) > 0:
        digits.pop()
        k -= 1
    
    # if the stack is empty, return zero
    if len(digits) == 0:
        return "0"
    
    # otherwise, return the digits in the stack as a string
    return str(int("".join(digits)))

1