algoadvance

Leetcode 402. Remove K Digits

Problem Statement

Given a non-negative integer represented as a string num, and an integer k, remove k digits from the number so that the new number is the smallest possible. Return the new number as a string, removing any leading zeros. If the result is an empty string, return “0”.

Example:

Input: num = "1432219", k = 3
Output: "1219"

Input: num = "10200", k = 1
Output: "200"

Input: num = "10", k = 2
Output: "0"

Clarifying Questions

  1. Q: What is the range of the inputs? A: The length of num is between 1 and 100,000. The value of k is between 0 and the length of num.

  2. Q: Can num contain leading zeros initially? A: No, the number will not contain leading zeros initially, although the resulting number should remove leading zeros.

  3. Q: What if k is 0? A: If k is 0, the input number should be returned as it is.

  4. Q: What if k is equal to or larger than the length of num? A: The result should be “0”, since removing all digits will leave us with an empty number.

Strategy

  1. Use a monotonic stack to keep the digits of the smallest possible number.
  2. Traverse each digit in the input string:
    • While digits in the stack can be popped (i.e., the current digit is smaller than the top of the stack) and k is still positive, pop the stack to build the smallest possible number.
    • Push the current digit onto the stack.
  3. If there are still more digits to be removed (i.e., k is still positive), remove them from the end of the stack.
  4. Build the resultant number from the stack.
  5. Remove leading zeros from the resultant number.
  6. If the resultant number is empty after leading zeros removal, return “0”.

Code

#include <iostream>
#include <string>
#include <deque>

class Solution {
public:
    std::string removeKdigits(std::string num, int k) {
        std::deque<char> stack;
        
        for (char digit : num) {
            while (!stack.empty() && k > 0 && stack.back() > digit) {
                stack.pop_back();
                k--;
            }
            stack.push_back(digit);
        }
        
        // If k is still greater than 0, remove the remaining digits from the end
        while (k > 0) {
            stack.pop_back();
            k--;
        }
        
        // Build the result from the stack and remove leading zeros
        std::string result = "";
        bool leadingZero = true;
        for (char digit : stack) {
            if (leadingZero && digit == '0') continue;
            leadingZero = false;
            result += digit;
        }
        
        return result.empty() ? "0" : result;
    }
};

// Example usage:
int main() {
    Solution sol;
    std::string num1 = "1432219";
    int k1 = 3;
    std::cout << sol.removeKdigits(num1, k1) << std::endl; // should return "1219"
    
    std::string num2 = "10200";
    int k2 = 1;
    std::cout << sol.removeKdigits(num2, k2) << std::endl; // should return "200"
    
    std::string num3 = "10";
    int k3 = 2;
    std::cout << sol.removeKdigits(num3, k3) << std::endl; // should return "0"
    
    return 0;
}

Time Complexity

The solution efficiently uses a monotonic stack to ensure we are constructing the smallest possible number while adhering to the requirement of removing k digits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI