algoadvance

Leetcode 402. Remove K Digits

Problem Statement

Given a non-negative integer num represented as a string and an integer k, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be >= k.
• The given num does not contain any leading zero except for the zero itself.

Example:

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.

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.

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is "0".

Clarifying Questions

1. Q: What should be returned if all digits are removed? A: The result should be “0”.

2. Q: Are there any constraints on how to handle leading zeros? A: The resulting number should not have any leading zeros unless it is “0”.

3. Q: Should we consider optimizing for very large input sizes close to the upper constraints? A: Yes, the solution should be efficient for input sizes close to the upper limits.

Strategy

1. Use a Stack:
   • Use a stack to build the smallest number by removing digits in a greedy manner.
   • Iterate through each digit.
   • Use the stack to keep the digits in ascending order, removing larger digits when necessary.
   • Ensure to handle cases where excess digits need to be removed.
2. Construct Result:
   • After processing all digits, the stack will contain the digits of the resulting smallest number.
   • Convert the stack back to a string and remove leading zeros.
3. Edge Cases:
   • If k is equal to the length of num, the result is “0”.
   • Handle scenarios where leading zeros might be formed and ensure they are stripped.

Code

import java.util.Stack;

public class Solution {
    public String removeKdigits(String num, int k) {
        int len = num.length();
        if (k == len) { 
            return "0"; 
        }

        Stack<Character> stack = new Stack<>();
        for (char digit : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }

        // Ensure to remove any remaining digits if k > 0
        while (k > 0) {
            stack.pop();
            k--;
        }

        // Build the result string from stack
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        result.reverse();

        // Remove leading zeros
        while (result.length() > 1 && result.charAt(0) == '0') {
            result.deleteCharAt(0);
        }

        return result.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.removeKdigits("1432219", 3)); // Output: "1219"
        System.out.println(solution.removeKdigits("10200", 1)); // Output: "200"
        System.out.println(solution.removeKdigits("10", 2)); // Output: "0"
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the input string num.
  • Each digit is processed at most once and stack operations (push/pop) are O(1).
• Space Complexity: O(n), where n is the length of the input string num.
  • Stack space in the worst case for storing the digits of the result without intermediate removals.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?