LeetCode Solutions Blog

Remove K Digits

Number: 402

Difficulty: Medium

Paid? No

Problem Description

Given a string representing a non-negative integer and an integer k, remove k digits from the string such that the resulting number is the smallest possible. The output should not contain any unnecessary leading zeros; if the number is reduced to nothing, return "0".

Key Insights

Use a greedy approach that removes digits to make the number as small as possible.
Utilize a stack (monotonic increasing sequence) to decide whether to keep or remove a digit.
Remove any excess digits from the end if k > 0 after the primary loop.
Handle edge cases including leading zeros and the possibility of removing all digits.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(n), needed for the stack.

Solution

We apply a greedy algorithm using a monotonic stack. For each digit in the number, if the current digit is smaller than the last digit on the stack and we still have removals (k > 0), we pop from the stack. This removal helps in making the constructed number smaller. After iterating over the entire number, if any removals remain, we trim the number from the end. Finally, we join the resulting digits, strip leading zeros, and if the result is empty, we return "0".

Code Solutions

# Python solution with line-by-line comments
def removeKdigits(num: str, k: int) -> str:
    # Initialize a stack to build the final number.
    stack = []
    
    # Traverse each digit in the input number.
    for digit in num:
        # Remove digits from the stack if the current digit is smaller,
        # making sure we still have removals available.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        # Append the current digit to the stack.
        stack.append(digit)
    
    # If there are still removals left, remove digits from the end.
    while k > 0:
        stack.pop()
        k -= 1
    
    # Construct the result string and remove any leading zeros.
    result = ''.join(stack).lstrip('0')
    
    # Return "0" if the resulting string is empty.
    return result if result else "0"

# Example usage:
# print(removeKdigits("1432219", 3))  # expected output: "1219"