LeetCode 402: Remove K Digits Solution

Master LeetCode problem 402 (Remove K Digits), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

402. Remove K Digits

Medium

String Stack Greedy Monotonic Stack

Problem Explanation

Explanation:

The key idea to solve this problem is to remove digits from the number while ensuring that the resulting number is the smallest possible. We can achieve this by iteratively removing digits that are larger than the next digit to the right. This process ensures that the resulting number is as small as possible.

Here is a step-by-step approach to solving the problem:

Create a stack to store the digits of the number.
Iterate through each digit in the input number.
For each digit, remove any digits from the stack that are larger than the current digit and decrement k accordingly.
Push the current digit onto the stack.
If k is still greater than 0 after processing all digits, pop the last k digits from the stack.
Construct the final number by combining the remaining digits in the stack.
Remove any leading zeros from the final number.

Time Complexity: O(n), where n is the length of the input number. Space Complexity: O(n), where n is the length of the input number.

Solutions:

Solution Code

class Solution {
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }
        
        while (sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }
        
        return sb.toString();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 402 (Remove K Digits)?

This page provides optimized solutions for LeetCode problem 402 (Remove K Digits) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 402 (Remove K Digits)?

The time complexity for LeetCode 402 (Remove K Digits) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 402 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 402 in Java, C++, or Python.

Back to LeetCode Solutions