Remove K Digits - Python Solution with O(n) Time Complexity

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.

Understanding the Problem

The core challenge of this problem is to remove k digits from the given number num such that the resulting number is the smallest possible. This problem is significant in scenarios where minimizing numerical values is crucial, such as in financial calculations or optimization problems.

Potential pitfalls include removing digits in a way that does not lead to the smallest possible number or ending up with leading zeros in the result.

Approach

To solve this problem, we need to think about how to remove digits in a way that minimizes the resulting number. A naive approach would be to generate all possible combinations of the number after removing k digits and then selecting the smallest one. However, this approach is not feasible due to its exponential time complexity.

Instead, we can use a greedy algorithm with a stack to achieve an optimal solution. The idea is to iterate through the digits of the number and use a stack to keep track of the digits of the resulting smallest number. We remove digits from the stack if the current digit is smaller than the top of the stack and we still have digits left to remove.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize an empty stack to keep track of the digits of the resulting number.
Iterate through each digit in the input number.
While the stack is not empty, the current digit is smaller than the top of the stack, and we still have digits left to remove, pop the top of the stack.
Push the current digit onto the stack.
If there are still digits left to remove after the iteration, remove them from the end of the stack.
Convert the stack to a string and remove any leading zeros.
If the resulting string is empty, return "0". Otherwise, return the resulting string.

Code Implementation

def removeKdigits(num: str, k: int) -> str:
    # Initialize an empty stack
    stack = []
    
    # Iterate through each digit in the input number
    for digit in num:
        # While the stack is not empty, the current digit is smaller than the top of the stack,
        # and we still have digits left to remove, pop the top of the stack
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1
        # Push the current digit onto the stack
        stack.append(digit)
    
    # If there are still digits left to remove, remove them from the end of the stack
    while k > 0:
        stack.pop()
        k -= 1
    
    # Convert the stack to a string and remove any leading zeros
    result = ''.join(stack).lstrip('0')
    
    # If the resulting string is empty, return "0". Otherwise, return the resulting string
    return result if result else "0"

Complexity Analysis

The time complexity of this approach is O(n), where n is the length of the input number. This is because each digit is pushed and popped from the stack at most once. The space complexity is also O(n) due to the stack used to store the digits of the resulting number.

Edge Cases

Potential edge cases include:

Removing all digits from the number, resulting in "0".
Handling leading zeros in the resulting number.
Input number with all identical digits.

These edge cases are handled by the algorithm as it ensures that the resulting number does not have leading zeros and returns "0" if all digits are removed.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small numbers and small k.
Cases with leading zeros in the input number.
Cases where all digits are removed.
Large input numbers to test the efficiency of the algorithm.

Using a testing framework like unittest in Python can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints thoroughly.
Consider both naive and optimized solutions.
Break down the problem into smaller, manageable parts.
Use data structures like stacks or queues to simplify the solution.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of removing k digits from a number to obtain the smallest possible integer. We explored a greedy algorithm using a stack to achieve an optimal solution with O(n) time complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills and optimizing numerical computations.

We encourage readers to practice and explore further to enhance their understanding and proficiency in algorithmic problem-solving.

Additional Resources

For further reading and practice problems related to this topic, consider the following resources: