We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove K Digits

Difficulty: Medium

Problem Description

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Key Insights

  • Removing digits should aim to create the smallest possible number.
  • A greedy approach can be used by maintaining a stack to keep track of the digits.
  • We can remove the top of the stack if the current digit is smaller than the stack's top and we still have k digits to remove.
  • After processing all digits, if there are still digits to remove, we can simply remove them from the end of the stack.
  • Leading zeros should be handled by converting the result to an integer and back to a string.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the input string. Space Complexity: O(n) - in the worst case, we may need to store all digits in the stack.

Solution

To solve the problem, we can use a greedy algorithm with a stack data structure. The algorithm works as follows:

  1. Initialize an empty stack.
  2. Iterate through each digit in the input string.
  3. For each digit, while the stack is not empty and the top of the stack is greater than the current digit, pop the stack if we still have k digits to remove.
  4. Push the current digit onto the stack.
  5. If there are still digits to remove after processing all digits, remove them from the end of the stack.
  6. Convert the stack back to a string, remove leading zeros, and return the result.

Code Solutions

def removeKdigits(num: str, k: int) -> str:
    stack = []
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    
    # If there are still digits to remove, remove from the end
    stack = stack[:-k] if k else stack
    
    # Convert stack to string and remove leading zeros
    return ''.join(stack).lstrip('0') or '0'
← Back to All Questions