Remove K Digits - Time Complexity: O(n), Language: C++

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 exactly 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 find 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 efficiently determine which digits to remove. The idea is to maintain a stack of digits and ensure that the digits in the stack form the smallest possible number.

Naive Solution

The naive solution involves generating all possible combinations of the number after removing k digits and then finding the smallest one. This approach is not optimal due to its exponential time complexity.

Optimized Solution

The optimized solution uses a stack to keep track of the digits. We iterate through each digit in the number and use the stack to ensure that the digits form the smallest possible number. If the current digit is smaller than the top of the stack, we pop the stack (remove the top digit) and push the current digit. We repeat this process until we have removed k digits.

Algorithm

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

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

Code Implementation


#include <iostream>
#include <string>
#include <stack>
using namespace std;

string removeKdigits(string num, int k) {
    stack<char> st;
    for (char digit : num) {
        // Remove digits from the stack if they are larger than the current digit
        while (!st.empty() && k > 0 && st.top() > digit) {
            st.pop();
            k--;
        }
        st.push(digit);
    }
    
    // Remove remaining digits if k > 0
    while (k > 0) {
        st.pop();
        k--;
    }
    
    // Construct the resulting number
    string result = "";
    while (!st.empty()) {
        result = st.top() + result;
        st.pop();
    }
    
    // Remove leading zeros
    int start = 0;
    while (start < result.size() && result[start] == '0') {
        start++;
    }
    result = result.substr(start);
    
    // If the result is empty, return "0"
    return result.empty() ? "0" : result;
}

int main() {
    string num = "1432219";
    int k = 3;
    cout << "Result: " << removeKdigits(num, k) << endl; // Output: "1219"
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n), where n is the length of the 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.

Edge Cases

Potential edge cases include:

Removing all digits (e.g., num = "10", k = 2 should return "0").
Leading zeros in the result (e.g., num = "10200", k = 1 should return "200").
All digits are the same (e.g., num = "1111", k = 2 should return "11").

Testing

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

Simple cases with small numbers.
Cases with leading zeros.
Cases where all digits are removed.
Cases with large numbers to test performance.

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.
Use data structures like stacks to simplify the problem.
Test the solution with various edge cases.

Conclusion

In this blog post, we discussed the problem of removing k digits from a number to form the smallest possible number. We explored a naive solution and an optimized solution using a stack. We also analyzed the complexity and discussed edge cases and testing strategies. Understanding and solving such problems is crucial for developing strong problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: