DEV Community

codechunker
codechunker

Posted on

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

#leetcode #algorithms #codenewbie #tutorial

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"; }
Enter fullscreen mode Exit fullscreen mode

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(); }
Enter fullscreen mode Exit fullscreen mode

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)