I didn’t know how to solve this Leetcode Problem!😭😭😭

This is a medium Leetcode 402 question where you are asked to remove k digits from a number to make that number the smallest possible number. See problem description below:

problem description

The question is quite understandable and straight forward but the issue is with knowing the numbers to remove. At first, I thought that sorting the numbers and keeping track of the positions and then removing the largest numbers would work but apparently that didn’t work.

After trying to no avail, I had to seek for solution online and came across two algorithms:

FIRST ALGORITHM

public static String removeKdigits(String num, int k) {
    Stack<Character> stack = new Stack<>();
    StringBuilder answer = new StringBuilder();
    if (num.length() == k) return "0";

  for (int i = 0; i < num.length(); i++) {
   while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)) {
            stack.pop();
            k = k - 1;
        }
        stack.push(num.charAt(i));
    }

    while (!stack.isEmpty()) {
        answer.append(stack.pop());
    }

    if (!answer.toString().isEmpty()) {
        answer = answer.reverse();
        String s = answer.toString().replaceFirst("^0+(?!$)", "");
        if (k != 0)
            s = s.substring(0, answer.length() - k);
        return s;
    } else
        return "0";
}

To understand the algorithm above, please check thecodingworld on YouTube. He did a good job to explain the algorithm. His code was written in Python, so I had to translate to Java.

SECOND ALGORITHM

public static String  removeKdigits(String num, int k) {
    Stack<Character> stack =  new Stack<>();
    int length = num.length();
  for (int i = 0; i < length; i++) {
   while (!stack.isEmpty() && k > 0 && stack.peek() > num.charAt(i)) {
            stack.pop();
            k -= 1;
        }

        if (!stack.isEmpty() || num.charAt(i) != '0')
            stack.push(num.charAt(i));
    }

    //Now remove the largest values from the top of the stack
    while (!stack.empty() && k != 0) {
        stack.pop();
        k--;
    }


    if (stack.isEmpty())
        return "0";
    
    //now retrieve the number from stack into a string
    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    return result.reverse().toString();
}

Also to understand the second algorithm above, please check Tech Dose for the explanation. I also translated the code to Java.

OBSERVATION

I have learnt a lot from these algorithms especially from the way people think and I think that’s the fun of solving algorithm questions.

Thank you for reading. Please leave a comment or suggestion below.