Minimum Operations to Convert All Elements to Zero - Leetcode 3542 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem minimum operations to convert all elements to zero. And before I get into it, the one thing I can tell you about this problem and just like my general tip of the day is sometimes you have to come up with your own examples to be able to figure out the intuition behind a problem and the solution. Don't over rely on the examples that leak code gives you or in a real interview the examples that your interviewer gives you. Why not come up with your own examples? I know it takes a little bit of effort, but it's the only way you can solve problems like these in my opinion. The idea is we're given an array of nums. They're all non- negative. Now, that doesn't mean they couldn't be all zeros, but still they're definitely not going to be negative. And we want to apply certain operations to make the entire array equal to zero. The operation that we're allowed to do is to take any subarray and set all occurrences of the minimum value. So first among that subarray we find the minimum value. In this case it's one and then we set all of them to zero. So this is going to become a zero. Now now what would happen if we tried to pick the exact same subarray? You might think okay well now it's going to go to the next smallest which in this case is two. No. The most important thing to recognize is now the minimum of this subarray is zero. If we pick the exact same subarray or even if we pick a subarray that includes the exact same element, it's not going to do anything because it's going to say this is the minimum element. Reassign it to zero. It's already zero. So basically the first observation you should make is once an element has become zero, we can never include that element again in any of the subarrays that we choose. And what we're trying to do in this problem is determine the minimum number of operations. So we definitely wouldn't want to waste an operation on something that does nothing. Now you can kind of let that thought marinate in your mind. But the next logical thing that you should arrive at is that if this is the case, well, how should we process the elements first? Because ideally we'd try to be greedy, right? Like why would I ever pick a subarray like this one that just has a single one when clearly there are multiple ones? If I pick the entire thing, I'll be able to get rid of both of these at the same time. So this leads you down the idea of a greedy solution. You might also consider well which order should we try to process the elements. Should we go for the ones first which is the smallest element in this case or maybe we should go for the two. And again this is a key observation you cannot miss. You have to do the smallest elements first. Why? Just use this as an example. What if we did the two first? Okay we we just do that. Well, we can't really include any more elements. we'd have to pick this subarray cuz we don't want either of these guys included. So, this will become a zero. That's great. But now we have to do the ones separately because we just created a hole. If I do this, it's not going to do anything. If I do this, it's not going to do anything. And if I do this, it's also not going to do anything. We can't include that zero anymore. So that's why we choose to do the smaller elements first because we want to minimize the chance that there's a hole in them and we can then process multiple of the smaller elements at the same time. Now it's still possible that we might create a hole by doing it this way. But still we're trying to try to get as many of them in the same operation as we can. Just to make it more clear I'll change the example a little bit. What if we had 2 two 1 2? You might think, well, I want to do all the twos at once. I'm trying to be greedy, but it doesn't work. You have to do the smallest element. Remember, that's why we do the smallest. We get rid of that into a zero. And then we can do this together. And then we can do this together. Well, it's just a single element, but I'm sure you get the point. So, those are some key observations. And once you understand those, the problem still doesn't become trivial because it's not going to be very efficient figuring out those subarrays and then actually doing those operations. So I'm going to use a different example now. So there's probably better examples, but this one will kind of help us understand uh the solution that I'm going to show like the algorithm and stuff. But I also want to bring up this idea of segments. Not segment tree. Don't get too nervous. but just that we have certain contiguous uh segments. So what's the solution to this problem going to be? Like that's not going to be too hard for you to figure out, right? Based on the observations I told you, you should be able to tell me what the solution is. Not necessarily the solution algorithm, but what's the solution to this problem? Let's just do it and let's make it color-coded. We know we want to be greedy. We want to do this segment first because then we can get rid of all of these ones. Next, we would want to be greedy and do the twos first. Unfortunately, we created a hole over here. We can't do the twos together. They're not adjacent. They form two separate segments. But, uh, even still, we can then get rid of them. And same thing now with three. Thankfully, uh, there's just a single three. If there were multiple threes, like if there was a three over here, we would not be able to extend it because again, there's a hole. Well, there's a bunch of holes now. But if the three was contiguous, like if there were two threes here, we would have been able to process them together. And actually, even if there was a three over here between the four and the hole, we would actually be able to do those two threes together because four is bigger than both of the threes. And we know that the minimum element is the one that becomes zero. So clearly the value and the order of the values matter when it comes to creating these segments or even I would say counting the segments right we can reframe the problem in terms of counting these segments that should hopefully lead you down the right track but again the solution is not obvious especially if you haven't seen it before and so now I'm just going to tell you what the solution is and I'm going to show you how nicely it fits in this problem because if you haven't heard of it, there's almost no chance you'd be able to figure it out. It's called the monottonic stack. Not super obvious how it applies, but I think when you start thinking of this in terms of counting the segments, it does become pretty natural. And let me just show you. I'm not even going to start with the stack idea. I'm just going to show you the logic when it comes to arriving at the idea of the stack. Watch this. And I didn't really finish the example, but obviously we'd have four in its own segment. So, let's uh consider this. Let's try to go from left to right and try to count the segments the best we can. Let's see if we can indeed do this in one pass. And we don't have to do any kind of nested stuff. We don't have to like update the values every time we pick a window. Is this even possible? Let's try it. So first element I see is three. So all I know right now is I have a three. If I were to see the next number now and the next number suppose it's a two, right? Let's suppose the four doesn't exist. Once I see the two, you tell me what do I know with 100% certainty. What do I know? Well, I know that this three and the segment that it belongs to stops right here because we know the solution to the problem is greedy. We know for sure that two is going to be gone before three. It's going to leave a hole right there. Doesn't matter how many threes come up next because we will not be able to connect them into the same segment. So if I saw a two, I know for sure we will stop. We don't have to track this three anymore. We don't really care about it. We can just say, okay, that was a single segment. But that's not what happens. Look what happens instead. We see a bigger number four. So now things are not certain. I don't really know anything with 100% certainty because I can't predict the future. I don't know what elements are coming up next. If the case is that the next element is a three, well then I do have to connect these two threes. But if the next element is a two, then I don't have to connect them and the segment will stop here. And I guess I kind of lied because actually we do know something else with 100% certainty. And maybe you actually already know what it is. But if we do see a number here that is bigger than three, well, we know with 100% certainty that these are going to be two different segments. And actually that's also true when it's a smaller number as well. If this was a two, we know for sure these are two separate segments. So we can keep track of the count of the segments. And that would be the case if they're different. Like obviously if this is a three, then we don't count it as a new segment. So now you might know what direction I'm going in. The stack, the monotonic stack is probably going to be an increasing order because as the elements are increasing, well, we're not really sure about what the future holds. But if the elements are in decreasing order, like if I see a three and a two, actually I don't really need to know what came before. If they were in decreasing order, we can just say, okay, well that three was in its own segment. We already know the end of that segment. We don't have to keep track of it anymore. So the stack is going to be in increasing order, and I guess the adjacent elements could also be equal as well. So that's mostly the intuition. Now, let me show you just kind of a quick dry run of this algorithm. And I'll keep track of the count of segments. And I'll keep track of the stack over here. I might just actually keep track of the stack like here. I'll just cross out elements once they become popped from the stack. I think that'll make it most intuitive. So let's uh do this. Let's start with three. Okay, we have three. Uh it's the first element we see. There's nothing on the stack yet. So we will increment the count to one. And now the next element is going to be four. So what we would do is compare this element. If our stack is non-MP, we would compare this to the previous element. And if the previous element was greater than this one, in other words, if this element is smaller than the previous element on the stack, then we would remove from the stack. And like I said, it could have been multiple elements. There could have been multiple threes. So maybe we'd pop both of them. Or maybe there could have been actually a two at the beginning, in which case we would have popped both of them. And it would have been fine to pop both because when we saw each element, we would have counted that as a segment. We would have counted three as a segment. So we would have had two segments there. And yes, we can pop them now because if this element was like a one and it was smaller than both of these, we know that we can't extend those segments. But that's not the case. We're dealing with a more simple example. So for now, we do not pop anything. We see that this is a different from the previous element. And thus we would increment the number of segments that we have. Now it's going to be two. And now we get to the more interesting case. This is our stack. So far we see a two. Okay. Okay, so now we're dealing with that example, that case that I talked about. Two is smaller than four. Okay, pop four. Two is smaller than three. Pop three. That means that this would have been its own segment. This would have been its own segment. And now we have a new segment. So let's increase the count to three. Now we have three segments total for sure. And now we see the next element. It's going to be a one. So once again, we will opt any further. This is where it's going to stop. We get rid of this. We do see that this is a different element though. And thus once again we increment the number of segments. Now we have four. And now it's going to get a little bit easier because now we see a two. Two is bigger than one. So no need to pop. But since it is a different element than before, we do increment the number of segments to be five. Next we see a one. So what that means is it's smaller than the previous. We pop that. We say that's its own segment. Uh but these two ones are still connected. And so since now this is the same as the element at the top of our stack after we're done popping. We actually do not increment the number of segments. This doesn't belong to a new segment. It belongs to the same one. Okay. Now we see four. That's good. Don't need to pop anything. And we since it's different than the top of the stack, we do increment the number of segments. It's going to be six. And lastly, we see the other one here. So we pop the previous element. And then we see this is the same as the top of the stack. So again, no new segment. We counted six total segments. We didn't even need to pop everything from the stack. So just to prove it to you, these are the segments. There's one here. Uh there's one here, one here. Uh this is four, and then this is one, and then this is one. We'd obviously have to do them in a particular order with the smallest elements going first, but there are six segments. Now there's one little edge case that's really really easy to miss and that is uh they do tell us that the input array could include some zeros. So it is worth exploring that edge case cuz it does lead to some problems because what should we do? Like first of all let's just make it really easy. What if the zero is at the end? That seems like it's a really trivial case to handle and it is but it's still easy to mess up. What would we do when we see the zero over here? Well we'd say that this is different from the top of the stack. So let's increment the number of segments. it's going to be seven. Now, you probably think you're a genius, but no, that's actually a bug because we don't need to zero this out. It's already zero. And I personally made that mistake, so that's why I'm mentioning it. And so, that's also going to apply if the zero was somewhere in the middle, like if this was a zero. And what I mean is that uh it's going to handle two things. One is that we would not count this as a new segment. That's for sure. But if we do see this zero, well, it is true that the previous number is bigger than it. And so that tells us that these two ones can't be connected. And so that is the case. So you do have to handle the zeros in a very particular way. You don't increment the count. But in terms of popping from the stack, we do need to account for the zeros. So I think it's pretty clear that this algorithm is going to be linear time because we're only pushing and popping from the stack. Like each element is only going to be pushed and popped a single time. N is the size of the input array. Let's code it up now. So, I don't know if this comment is helpful, but I'll leave it there just so you can kind of still look at the example as we're coding this. So, I'm going to have my stack. It's going to be an empty array initially. And I'm going to have my result, which is going to keep track of the count of segments. And then I'm just going to iterate over every number in nums. And the first phase is pop bigger previous elements because we cannot extend those segments any further. So we'll first check the stack is non-MP and then we'll check that the top of the stack is indeed bigger than the current element. So that's going to be like this actually. And if that's the case, all we need to do is pop. Notice how I didn't check if this is a zero yet. It doesn't matter if it's a zero. We'd still pop anyway. But next, the next phase of the algorithm would look like this. if the current number is different uh than the top of the stack. So we do that like this. If that's the case, well, first of all, we would know that the number and it's going to be n. Actually, I don't know what I'm doing. If that number is different, well, since we just popped all the bigger previous elements, that means that this element is smaller anyway. So, we would definitely push it. And you can even change the condition if you want. You can change it to this. It'll work the same. And actually, I guess this is technically more correct. So, I'll leave it this way. But it'll work in both ways. So I'll leave it like this. Uh but if that's the case, we know that this is a different segment now and we know that we should probably push it to the stack just like this. Now there's a bug here and that's what if the stack is empty. Well, if the stack is empty, we would definitely do this anyway. So let's just check that. If stack is non empty or or sorry if the stack is empty, if not stack or this is the case. So if the stack is empty, this part won't even evaluate in Python. So it won't give us a bug. It won't give us like an out-of- bounds error. But like I said, the edge case is what if n was a zero. And you can add to this if statement to uh protect against that. You could also just add an if statement here like if n is equal to zero then just continue to the next iteration of the loop. Or you could say if n is greater than zero and this is the case then do this. Either of these are fine. Maybe you preferred this one, but I'll just do this. And I'll give this a run. Okay, a really sloppy bug. Don't know why I put S there. And let's just change that to stack and get this to work. Okay, unfortunately, I think I had another sloppy bug. And that was actually with this comparison. I think it'll work if we do it this way. So, I'll just run it to make that clear. So, you can see here it does work. And it'll work when the condition is flipped from what I originally had. So, I just had the comparison going the wrong way because remember that if we popped all the bigger elements, well, we want our stack to be an increasing order. So, we would only want the end to be added if it's bigger than the previous one. So, that's the case. Again, apologies for that. I'm sorry if it made things confusing. So, you can see that also works. If you found this helpful, check out neat code.io for a lot more. Thanks for watching and I'll see you guys