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:
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.
Top comments (0)