[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.
This is why just removing digits purely on either the significant place or their absolute value does not work. Instead, we want to hit certain conditions (index), and remove the biggest values we have seen up to that point. Keep that in your mind as we proceed.
Let’s go back to the previously solved examples. Notice that Type-1 and Type-2 strings are mirrors of each other. Which checks out in their optimal solutions are the opposites. For Type-1, we remove the last k digits. For Type-2, it’s the first k digits that get axed.
Every mixed string can be broken down as a mix of Types 1&2 substrings. For example, 123984 is 1239(1)-84(2). And this transition b/w Type 1 & 2 is the perfect place to target. In our example, that is 8. Every value before 8 is in increasing order. However, 9 becomes smaller than 8. So we can remove 9, which is the largest value we have seen till now. And this checks out
For Types 1 and 2, we can quickly verify this. In either case, we would traverse the whole string (since there is no transition). But in the end, we will still remove the largest (k-largest) digits.
Does this work for other cases? Let’s invert our earlier pattern first. For the input 841239 our breakdown is 84(2)-1239(9). When we hit that transition, our algorithm will remove 8 first. Which is what we want (when k=1). But what about greater values of k?
For k=2, our algorithm will remove 8 and 4. No problems, exactly what we want. For more than 2, we can simply wait to keep building up the list of what we have seen and work it at the end. This works.
It is simple to verify this for more complex strings (multiple transitions). As long as you can break a string into transitions, and start removing the largest elements seen before every transition.
We have a solution. It works. But some of you may be wondering what Monotonic Stacks are and where they apply to this problem. Well, they show up in everyone’s favorite step- Optimization.
Step 4: Optimization
Our transition-reliant solution works perfectly for all input. However, every time we hit a transition, we have to go back and find the largest elements. This would be simple if the preceding substring was a type-1 since we could simply shave off the last elements.
Here is where we pull a neat trick. We evaluate Type-2 strings (and substrings) as Type-1. How do we do this? Take the type-2 “321”. This can be seen as 3(1)-2(1)-1(1). Basically, we say that we digit is a type-1 string followed by a transition. This way, we keep shaving of the last digit seen (which we know will be the biggest). And since we already proved that our solution will work for an arbitrary combination of transitions, we know that our code will work.
This is where the monotonic stack becomes helpful. Since every string becomes either a Type-1 or a combination of Type-1 Strings, we know that the last digit seen is the “heaviest” in the string. So we can simply call the pop function on the stack. Every time we see a value smaller than the top of the stack, we know that’s a transition and start our removal. Since we only push when the increasing order is maintained, the stack is guaranteed to be monotonic.
Our code will look like this. Take a look at all the little edge cases and little optimizations we fixed. This is a greedy solution since we are traversing the string one at a time and only looking at the top elements.
def removeKdigits(self, num: str, k: int) -> str:
size = len(num)
if size == k: return '0'
stack = []
for i, n in enumerate(num):
while stack and k and stack[-1]>n:
stack.pop()
k-=1
stack.append(n)
if len(stack)==1 and stack[-1] == '0':
stack.pop()
if not k:
res = ''.join(stack)+num[i+1:]
return str(int(res)) if res else '0'
while k:
n=''.join(map(str,stack))
if(n=='' or int(n)==0):
return '0'
stack.pop()
k-=1
return str(int(''.join(stack))) Our time complexity is linear since we are traversing through the numbers once (the benefit of the stack). Similarly, our space is O(N) since we have an additional stack.
If you liked this solution, please like the substack post. It really helps promote the newsletter to more people. Share this with others who might be interested.
Bonuses/Promotion (Get Free Stuff)
To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.
For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.
To share interesting problems/solutions 2with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75
Great solution. Your explanations of why Monotonic Stacks should be used is clear.