[Solution]Problem 26: Remove K digits to create smallest number[Microsoft]
String Manipulation, Integer Typecasting, Greedy Approach, Removing
Problem
This problem was asked by Microsoft.
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Example 1
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.
Example 2
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.
Example 3
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
PS: This problem is one of the trickiest problems out there. But I’m sure you will learn a lot from this solution. You can thank of the subs for this question request
Step 1: Working through a few samples
This is a relatively straightforward problem to understand. Unlike many other problems, you won’t struggle to understand the nuances of such a problem.
In such cases, one of the best things you can do to start solving the problems is to start working through a few samples. Working through some sample inputs can be a great way to build up the intuition for your solution. So how do we pick the best sample solutions?
The way I have found most useful is through analyzing the input. Look at it and see what kinds of input we can have. For example, our string can represent numbers of 3 types:
String where the digits are sorted in ascending order - such as “1234”
Strings sorted in descending order - “4321”
Mixed up strings- “1432219”, taken from example 1. This includes leading 0s, although we might probably want to handle them separately.
For simplicity’s sake, assume we have a k=1.
When our string is Type-2, we can get the smallest possible number by removing the 4. This is because if remove any other number, we end up with 4__ which is bigger than 321 (what we get when we remove 4).
In fact, for Type-2 strings, you can notice something amazing. For any given k, we create the smallest by removing the first k elements. Take a second to verify that.
This might give us a hint about the pattern. Maybe something greedy where we remove either the largest digit(s) in the string or the digits in the most significant places (notice that Type-2 Strings are both)? We can run it through our other samples.
Step 2: Pattern Discovery
We were able to see that either the significant place and/or the largest digit might have something to do with our solution. Both these factors intuitively make sense. Let’s refine our solution. Take our next type, Type-1 strings.
For the value 1234, what happens if we try to remove digits from the most significant place? For k=1, we end up with 234. Is this the smallest possible number? Well if we remove one of the other (bigger) digits, then we will end up with 1__ which will be smaller than 234. Through some trial and error, removing 4 (the largest digit), gives us 123, the smallest possible number.
Is this it? If our k was 2, then the smallest would be 12, which is what we would get from removing the largest digits. Have we finally discovered the pattern? Let’s test this on the final type of string.
We can use the test case given to us, and use the result of that to build our solution. However, I will not do that. Why? Because that example is very helpful. Not every interviewer is likely to give us an example that is that useful. So to prepare for the worst case, let’s proceed without it while building up our solution.
Let’s take a simpler example, num= “432891”; k=1. Here it is very clear that blindly removing the biggest digit will not result in the smallest possible answer (43281 > 32891). In fact, removing the most significant digit, did the trick. However, if the example was “1432891”; k=1 instead of removing the 1 (the most significant digit), we still want to remove 4. So what is going on?
It’s clear that we want to remove the big digits at significant places. Instead of looking at only one of these elements, we want to consider them both. Some of you might be onto what we can do. Some of you probably have no idea.
Most tech blogs/videos covering this question just say that they will use the Monotonic Stack to solve the question. At best, they will work through some flimsy examples. Unfortunately, this won’t help people who haven’t come across many Mono-Stack Questions. Obviously, my subscriber agrees.
So, I will spend the next section explaining how someone with no knowledge of Mono-Stacks in Leetcode would be able to identify how to use them here.
Step 3: Recognizing the Pattern
As mentioned, most online resources don’t actually explain the why behind how they came up with their solution (probably because they don’t understand it themselves). I, however, am the most woke for a reason.
Let’s start simple again, with our good friend: “15234”. Let’s imagine you were to take out the 2. How does that really change the number?
The 1 and the 5 lose their value. More precisely, their values are divided by 10. However, the values of the 3 and 4 stay constant. This is true regardless of which digit you chose to remove. The digits to the left of it will see their value reduced by 10. The ones to the right will not see their values change.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.