Maximum Value of an Ordered Triplet II - Leetcode 2874 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve a problem. Maximum value of an ordered triplet 2. It's the exact same as the first problem, except the constraints are a bit more strict. I'm honestly not sure if the n squared solution that we wrote for the first variation of this problem would actually pass or not. Maybe it would, but why waste our time with that? I already covered it in the other video, so if you want to watch that, definitely check it out. Leak code 2873. I'd probably recommend checking it out before tackling this one. I'll assume that you've watched it. In this video, I'm going to be showing you the linear time solution. Believe it or not, it's actually very, very easy to code up. And it's actually very easy, I think, to understand once you kind of grasp your head around it. It is a greedy algorithm. I think the biggest issue people have with these solutions is just understanding why they work. Cuz this one's going to be pretty easy to code up. But understanding why is going to be the most important part. I'll try to cover that as best as I can. Let's take a look at this example. 12 6 1 2 and 7. Looks like the solution is 77. And that is this math formula that kind of got chopped off. So I just rewrote it down here because this is kind of the entire problem. We want to maximize this formula. The idea that we had was sort of that well we always want this to be as big as humanly possible right so as we're going through any time we see a new maximal value we're going to say it's going to be our i value now and then for that i value like let's say it's fixed or whatever so initially I guess this would be the i value then for k we're going to try to figure out all possibilities of it so j could be here. J could be anywhere. And then K is going to scan through and J is also going to be the outer loop. And anytime we find a new max with J, we assume that it's going to be our I value now. And if we don't find a new max, then we assume, okay, well, that value is going to be our J value. That's what allows us to get rid of that outermost loop, which keeps track of index I. But there's actually a better way to do this. We only need a single loop. And the idea is this. Well, we want to maximize this value over here, but at the same time, we want to minimize the value at index j. We don't want to just pick any random value. We want to minimize the value here. But, okay, that's where things get a little bit hairy. Things get tricky here because not only do we want to keep track of what our max we've seen so far. So, as I'm iterating, I get to this point. I say, "Okay, my biggest value was 12. That's the one I'm going to intelligently choose for this. I'm being greedy. But for the minimum, I could say, okay, well, my minimum so far is one, so that's the one I'm going to put over here. That's what's going to allow us to take this formula here and maximize it. But we have to be careful because we want the minimum value to always come after this one over here. So imagine like if this one over here instead it's maybe like a seven or something and then there was a one over there. For our max we would say it's 12 if we're at this point so far. For our minimum we would not say it's one because remember this value has to come after this one in the array. We would actually say our minimum so far is six. So be careful about that. Okay. That's kind of the entire intuition of this, believe it or not. But translating this idea into code requires some deliberate thought. As we fix this value and as we fix this value, what exactly are we iterating? I mean, what does our pointer even represent? Let's just call it uh pointer X right now because we don't know what it is. Is it I? Is it J? Or is it K? I don't know. But it's pointer X. What exactly does it represent? If I get to this point over here and I say, "Okay, so far my max is 12 and so far my minimum is 1." Well, it looks like x represents j similar to the n squ solution that we had in the last video. But actually, if we do that, well then we'll still have that second loop which is going to iterate over all of these possible values for this particular difference. But instead, if we do it a little bit differently, if we choose our pointer to actually be K, that allows us to do this in linear time. And it's not a coincidence. It's not a coincidence that we're choosing K. The reason we're doing K is remember that our pointers go like this. If I fixed my J pointer, I'd still have my K pointer iterating over the remainder of the array. And that's a problem because if we code it that way, we would expect our pointer to have to read through every future value. We can't predict the future. We don't know what values are coming. So that's why we intelligently choose our pointer to be K. Because let's say my K pointer over here, it's at two. I kept track of my maximum value. It was 12. I kept track of the minimum value that came after the max. It was one. We pick the last pointer because it allows us then to process all the elements we've seen before and from those elements to extract the information that we're actually looking for. So I think that's probably enough talking for me. Let me give you a quick dry run and it'll probably all make sense. So let's do that very quickly. And by the way, I know I said that we're going to keep track of the max. I'm going to call that the prefix max. And we also said that we're going to keep track of the minimum value that comes after the prefix max. But I guess I kind of was a bit misleading because remember I mentioned that it's kind of hard to keep track of the minimum value and make sure that it only comes after the prefix max. So instead of doing that, recognize that over here the reason we're trying to minimize this value in the first place is we're trying to maximize everything that's in the parenthesis like the sum or the difference of this. So rather than keeping track of the minimum, we could proxy that by keeping track of I'm going to call it the max diff, which is basically what is over here. And we're going to initialize our max diff to be zero because if it ever became a negative value, we wouldn't really care about it anyway. So we can initialize our prefix max to be the first value here. So I'm going to say that's 12. And now I'm going to start iterating. I'm gonna have my K pointer actually start at the beginning, but I guess we probably wouldn't have to do that. We could just start it at the second value. So, I guess I'll do that. So, it'll start here. We already know our max so far that we've seen is the first value, whatever it happens to be. It's 12 in this case. Now, we're at six. So, the first thing we're going to do is take our current value, and this is our K value, and we're going to multiply it by our current max diff, which initially is zero. And we intentionally chose that because we know that when we're at the first element over here, we don't even have a triplet yet. So the formula is going to end up being zero multiplied by whatever is over here, but that's going to end up being zero anyway. So that's fine. After we do that, next we're going to update these values potentially. Well, is the max updated? No, it looks like it's not going to be updated. Okay. Is the max diff updated? Our max so far is 12. subtract from it this value because maybe this is the new minimum. We're basically just checking like is this a new minimum because if it is then our max diff will end up increasing. So we update this by taking 12 minus this it ends up being six. Yes, six is bigger than this value. So update it to be six. And our k value is going to be shifted over here. Now we're at one. We multiply one by our max diff. and we end up with six over here multiplied by one that's going to end up being six. So our result so far is going to be six. We could have initialized it to zero but now it's going to be six. What exactly does that represent? Well, that represents this triplet over here because the max diff came from this pair. Our k value is this. So it makes sense that if you took the difference between these and multiply by one, it's going to be six. So next k value over here now or actually before we shift the k value we might potentially update these values. Is prefix max updated? Of course not. Is the max diff updated? Well actually yes because we take 12 minus one we get 11. 11 is bigger than this. So go ahead and replace it. So now our k values over here at 2 take two multiply it by 11 we get 22. that is bigger than our current uh result. So we can update our result to be 22. And then is this a new minimum? Well, we can determine that by taking 12 minus 2 that's going to be 10. Nope, that does not update our maximum diff. So it stays the same. K value is going to finally be at the last element 7 multiply by 11, we get 77. And that is the result of this problem. The pair specifically would be this is K. This is obviously our I value and I think this was the one at J. So something like this. Now in this example, our max diff never got updated or sorry, our max uh prefix max never got updated. So what would that have looked like? You might not be fully convinced that all we need to do is keep track of the prefix max. So let me just kind of prove it to you. Let's replace uh this over here with like 21 or something just so we don't have to change this number. So imagine that we processed these elements and now we're here. Okay, this is going to be the new prefix max. But you might be thinking, well over here I had 12 minus 6. That would have been this portion and it would have ended up being six. But you might be thinking, okay, well if I set this to my prefix max, it's going to be 21. Now, well, how do I know that like the following values are going to end up maximizing this part? I mean, what if like let's replace this with like a 20 and let's also replace this with a 20 just for simplicity. If this is my prefix max, then the max diff with this and the next guy is only going to be positive 1. And the max diff with this guy and this guy is only going to be positive 1. So, it seems like I kind of went backwards. Before I had it so good. I had 12 minus 6, which gave us a positive 6 over here. So, why did I ruin everything by picking this as my new maximum? Well, my brother in Christ, let me tell you, we already processed this part. This would have been like a positive 6 and it would have been multiplied by the value that came after it. But if I had kept 12 as the prefix max, well, I mean, this is a 20 over here and this is a 20 over here. So, that would have ended up making this formula part negative. And you wouldn't have wanted that, would you? So, that's why we are being greedy with this. It's not super obvious to see sometimes. So that's why I wanted toh give this part of the explanation. But anyways, you can see we're only keeping track of a few variables over here, resulting in constant space, and we only iterate over the input once, resulting in linear time. Let's code this up. I'll keep this nice and short. We're just going to have our prefix max initially be the first element. We'll keep track of the max diff, initially, setting it to zero. We'll start our k pointer at one and then go up until the length of the array. Remember what we're trying to do to maximize the result is this. We're taking the max of itself and the max diff we've seen so far multiplied by the current element k because we're considering this to be our last element. What's the max we could calculate where this is the last element. But after we're done with that, we want to potentially update these variables over here. And the order that we do them in does actually matter. I could update my max diff first. I could do something like this. Max diff is equal to the max of itself as well as the prefix max minus uh the current element. Possibly the current element uh if that is treated as the J value could end up making this bigger. And actually now that I'm thinking of it, I don't think the order actually does matter. So, I guess I kind of taught myself something as I'm going through this, which kind of makes you realize that even sometimes easy problems like this have some like interesting things about them. But we know we were going to update the max diff. And we also know we were going to update the prefix max. Let's do that after. So, prefix max updating that is pretty trivial. You just take the max of itself as well as the current element at K. Now, why is it that it doesn't matter what order that we put these in? Well, suppose that we did indeed reach a new prefix max. So, this is going to end up updating the prefix max. What would have happened to this code over here? Well, it would have taken the smaller prefix max and subtracted from it a bigger number, making this negative, but that wouldn't have done anything because our max diff would still be zero. And then after that, we would have updated our prefix max. Now, why is it appropriate to put this after? Well, because if we end up updating our prefix max, we found a new bigger number. Well, then at this point in time, we haven't seen any numbers that come after this one uh that are smaller. So, it makes sense for this to be zero. Now, if you swap the order of these, it still works because if you end up updating the prefix max, once again, this code would end up making this a zero anyway. If you don't end up updating the prefix max, well then it doesn't really matter what order these would be in. So let's go ahead and run this. You can see here it works and I believe this is the optimal solution. If you found this helpful, check out necode.io for a lot more. Greedy problems can be pretty tricky. I have a really good greedy playlist on necode.io. It's free. I would personally check out the Node 250, but if you're pretty skilled, the N code 150 is also fine.