HomeLeetcode402. Remove K Digits - Leetcode Solutions

402. Remove K Digits – Leetcode Solutions

Description

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Examples:

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.

Solution in Python

Approach

  1. Monotonic Stack:
    • Use a stack to keep track of digits of the resulting number in a way that the digits in the stack are in increasing order.
    • When processing each digit, if the digit is smaller than the top of the stack and we still need to remove more digits (k>0), pop the stack.
  2. Remove Remaining Digits:
    • After processing all digits in the input string, if k>0, remove the remaining k digits from the top of the stack.
  3. Construct the Result:
    • Convert the stack to a string. Remove any leading zeros to ensure the output is a valid number. If the result is an empty string, return “0”.
  4. Constraints:
    • Handle edge cases such as k=len(num) (all digits removed) or strings with leading zeros after removal.
Python
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # Stack to store the digits of the resulting number
        stack = []
        
        # Step 1: Process each digit in the number
        for digit in num:
            # Remove digits from the stack if they are larger than the current digit
            # and we still need to remove more digits (k > 0)
            while stack and k > 0 and stack[-1] > digit:
                stack.pop()
                k -= 1
            
            # Add the current digit to the stack
            stack.append(digit)
        
        # Step 2: If there are still digits to remove, remove them from the end of the stack
        while k > 0:
            stack.pop()
            k -= 1
        
        # Step 3: Construct the result by joining the stack
        # Remove leading zeros by converting to an integer and back to a string
        result = ''.join(stack).lstrip('0')
        
        # If the result is empty, return "0"
        return result if result else "0"

Detailed Explanation

  1. Building the Stack:
    • As we iterate through the digits in num, we ensure that the stack remains monotonically increasing by popping elements that are greater than the current digit. This guarantees that the resulting number is minimized.
    • The condition k > 0 ensures that we only remove digits while we are allowed to.
  2. Removing Excess Digits:
    • If k>0 after processing all digits, we remove the remaining k digits from the top of the stack.
  3. Handling Leading Zeros:
    • After constructing the number from the stack, use .lstrip('0') to remove any leading zeros.
    • If the resulting string is empty, return “0” as the smallest number.
  4. Edge Cases:
    • If k=len(num), all digits are removed, and the result is “0”.
    • If the input number has no digits after removal or is reduced to zeros, return “0”.

Solution in C++

C++
class Solution {
public:
    string removeKdigits(string num, int k) {
        // If k is equal to or greater than the size of the number, remove all digits
        if (k >= num.size()) 
            return "0";

        // Stack to keep track of the smallest number
        stack<char> st;

        // Iterate over each digit in the input number
        for (char digit : num) {
            // Remove digits from the stack if the current digit is smaller than the top of the stack
            // and we still need to remove more digits
            while (!st.empty() && k > 0 && st.top() > digit) {
                st.pop();
                k--; // Decrease the count of digits to remove
            }

            // Push the current digit onto the stack
            st.push(digit);
        }

        // If we still need to remove more digits (k > 0), remove them from the end of the stack
        while (k > 0 && !st.empty()) {
            st.pop();
            k--;
        }

        // Build the resulting number from the stack
        string result = "";
        while (!st.empty()) {
            result += st.top();
            st.pop();
        }

        // The digits are in reverse order, so we need to reverse the string
        reverse(result.begin(), result.end());

        // Remove leading zeros, if any
        int start = 0;
        while (start < result.size() && result[start] == '0') {
            start++;
        }

        // If the result is empty after removing leading zeros, return "0"
        if (start == result.size()) 
            return "0";

        // Return the final result
        return result.substr(start);
    }
};

Solution in Javascript

JavaScript
var removeKdigits = function(num, k) {
    // Edge case: If k is equal to the length of the number, return "0"
    if (k === num.length) {
        return "0";
    }

    // Initialize an empty stack to keep track of digits
    const stack = [];

    // Loop through each digit in the input string
    for (let digit of num) {
        // Remove digits from the stack while the following conditions are met:
        // 1. There are still digits to remove (k > 0)
        // 2. The current digit in the stack is greater than the current digit in the loop
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop(); // Remove the top digit from the stack
            k--; // Decrease the count of digits to remove
        }

        // Push the current digit to the stack
        stack.push(digit);
    }

    // If there are still digits left to remove (k > 0), remove them from the end of the stack
    while (k > 0) {
        stack.pop();
        k--;
    }

    // Join the remaining digits in the stack to form the resulting number
    // Use `replace` to remove leading zeros, if any
    const result = stack.join('').replace(/^0+/, '');

    // If the result is an empty string after removing leading zeros, return "0"
    return result === '' ? "0" : result;
};

Solution in Java

Java
class Solution {
    public String removeKdigits(String num, int k) {
        // Edge case: If k is equal to the length of num, we remove all digits and return "0".
        if (k == num.length()) {
            return "0";
        }

        // Use a StringBuilder as a stack to store the digits of the resulting number.
        StringBuilder stack = new StringBuilder();

        // Iterate through each digit in the input string.
        for (char digit : num.toCharArray()) {
            // Remove the top digit from the stack if it's greater than the current digit
            // and we still have digits left to remove (k > 0).
            while (stack.length() > 0 && k > 0 && stack.charAt(stack.length() - 1) > digit) {
                stack.deleteCharAt(stack.length() - 1); // Pop the top of the stack.
                k--; // Decrement k as we've removed one digit.
            }

            // Append the current digit to 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.length() > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }

        // Remove any leading zeros from the stack.
        while (stack.length() > 0 && stack.charAt(0) == '0') {
            stack.deleteCharAt(0);
        }

        // If the stack is empty after processing, return "0".
        if (stack.length() == 0) {
            return "0";
        }

        // Convert the stack to a string and return it.
        return stack.toString();
    }
}

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular