Code Implementation

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        # If k > 0, remove from the end
        final_stack = stack[:-k] if k else stack
        # Strip leading zeros
        result = ''.join(final_stack).lstrip('0')
        return result if result else '0'
      

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char> stack;
        for (char digit : num) {
            while (k > 0 && !stack.empty() && stack.back() > digit) {
                stack.pop_back();
                k--;
            }
            stack.push_back(digit);
        }
        // Remove from the end if k > 0
        while (k-- > 0) stack.pop_back();
        // Build result and remove leading zeros
        string result(stack.begin(), stack.end());
        int nonZero = 0;
        while (nonZero < result.size() && result[nonZero] == '0') nonZero++;
        result = result.substr(nonZero);
        return result.empty() ? "0" : result;
    }
};
      

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stack = new StringBuilder();
        for (char digit : num.toCharArray()) {
            while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > digit) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            stack.append(digit);
        }
        // Remove from the end if k > 0
        stack.setLength(stack.length() - k);
        // Remove leading zeros
        int i = 0;
        while (i < stack.length() && stack.charAt(i) == '0') i++;
        String result = stack.substring(i);
        return result.isEmpty() ? "0" : result;
    }
}
      

var removeKdigits = function(num, k) {
    const stack = [];
    for (let digit of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    // Remove from end if k > 0
    stack.splice(stack.length - k, k);
    // Remove leading zeros
    let result = stack.join('').replace(/^0+/, '');
    return result === '' ? '0' : result;
};
      

Problem Description

You are given a non-negative integer represented as a string num and an integer k. Your task is to remove exactly k digits from num so that the resulting number is the smallest possible (also as a string).

• You must not change the order of the remaining digits.
• If the resulting number has leading zeros, remove them.
• If all digits are removed (result is empty), return "0".

Constraints:

• 1 ≤ num.length ≤ 10⁵
• 0 ≤ k ≤ num.length
• num consists only of digits 0-9 and does not have leading zeros (except for "0" itself).

Thought Process

At first glance, the problem seems to suggest that we need to try all possible ways to remove k digits and pick the smallest result. But with large inputs, this brute-force approach is infeasible.

The key insight is that to make the smallest number, we want to remove digits that are "larger" and appear before "smaller" digits. In other words, whenever a digit is greater than the digit immediately after it, removing it can give us a smaller number. This leads us to a greedy approach.

Think of the number as a stack of digits. As we scan from left to right, we remove the previous digit if it's larger than the current one and we still have digits left to remove (k > 0). This ensures that bigger digits are removed from the left, making the number as small as possible.

After processing, if we still have digits to remove (i.e., k > 0), we remove them from the end, since the remaining digits are already in increasing order.

Finally, we must handle leading zeros and the case where all digits are removed.

Solution Approach

• Initialize a stack: This will help us build the smallest number by keeping track of digits in order.
• Iterate through each digit in num:
  • While k > 0, the stack is not empty, and the last digit in the stack is greater than the current digit, pop the last digit from the stack and decrement k.
  • Push the current digit onto the stack.
• Handle remaining removals: If k > 0 after the loop, remove digits from the end of the stack.
• Build the result: Join the digits in the stack to form the number.
• Remove leading zeros: Use string manipulation to remove any leading zeros.
• Return "0" if the result is empty: If all digits were removed or only zeros remain, return "0".

This approach is efficient because each digit is pushed and popped at most once, resulting in a linear time algorithm.

Example Walkthrough

Let's walk through an example with num = "1432219" and k = 3.

1. Start with an empty stack.
   Stack: []
2. Read '1': push to stack.
   Stack: [1]
3. Read '4': push to stack.
   Stack: [1, 4]
4. Read '3': 4 > 3 and k > 0, so pop 4 (k=2). Push 3.
   Stack: [1, 3]
5. Read '2': 3 > 2 and k > 0, so pop 3 (k=1). Push 2.
   Stack: [1, 2]
6. Read '2': 2 == 2, so push 2.
   Stack: [1, 2, 2]
7. Read '1': 2 > 1 and k > 0, so pop 2 (k=0). Push 1.
   Stack: [1, 2, 1]
8. Read '9': k=0, just push.
   Stack: [1, 2, 1, 9]
9. Join stack: "1219". Remove leading zeros (none). Return "1219".

Thus, the smallest number after removing 3 digits is 1219.

Time and Space Complexity

• Brute-force approach: Try all combinations of removing k digits from n digits. This would be O(C(n, k) \times n), which is exponential and infeasible for large n.
• Optimized stack-based approach:
  • Time Complexity: O(n), where n is the length of num. Each digit is pushed and popped at most once.
  • Space Complexity: O(n) for the stack to store the digits.

Summary

The "Remove K Digits" problem is elegantly solved using a greedy stack-based approach. By always removing the previous larger digit when possible, we ensure that the resulting number is the smallest possible. This method is efficient, easy to implement, and handles edge cases like leading zeros and complete removal gracefully. The key insight is to make local greedy choices that lead to the globally optimal solution.