Remove K Digits - JavaScript 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 of 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.
Construct the resulting number from the stack and remove any leading zeros.
If the resulting number is empty, return "0".

Code Implementation

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
function removeKdigits(num, k) {
    // Initialize an empty stack
    let stack = [];
    
    // Iterate through each digit in the number
    for (let digit of 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.length > 0 && k > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        // Push the current digit onto the stack
        stack.push(digit);
    }
    
    // If there are still digits left to remove, remove them from the end of the stack
    while (k > 0) {
        stack.pop();
        k--;
    }
    
    // Construct the resulting number from the stack and remove any leading zeros
    let result = stack.join('').replace(/^0+/, '');
    
    // If the resulting number is empty, return "0"
    return result === '' ? '0' : result;
}

// Example usage:
console.log(removeKdigits("1432219", 3)); // Output: "1219"
console.log(removeKdigits("10200", 1)); // Output: "200"
console.log(removeKdigits("10", 2)); // Output: "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.

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 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 values.
Cases with leading zeros in the input number.
Cases where all digits are removed.
Large input numbers to test performance.

Using a testing framework like Jest or Mocha 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 steps.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of removing k digits from a number to get 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 efficient algorithms and improving problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: