Apply Operations to Maximize Score - Leetcode 2818 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem. Apply operations to maximize score. This is definitely a difficult problem, but in some ways at least like how to think about a problem like this, I really really want you by the end of this video to realize that you do have some strategies. Even if you weren't able to solve this problem and even if you can't solve it or solve a problem like this in the future, I want you to know that you don't have to like blankly stare at the problem description. you do have things and the brute force solution I think if you are not able to come up with that one in this problem then that is really the first step because it's really not that difficult in my humble opinion I think that's like definitely a medium problem in some ways it's one of the easier medium problems if you're just implementing the brute force solution so let me start with that one and that does give us a bit of intuition on solving this a bit more optimally but I will say like the optimal solution it's definitely pretty difficult a lot of things a lot of observations you're going to have to make. But anyways, the idea here is that we are given an array of positive integers that look like this. And we are given an integer K. So K represents how many times we want to apply a specific operation. And they tell us what the operation is and how to do it. But what we want to do with the operation is try to maximize our score. Our score initially, let's say, is zero. We want to try to maximize that. So, we want to pick our operations intelligently. Oh, and actually, no, the score isn't zero. It's actually one. And that's going to matter because when we choose an operation, we're going to actually multiply this number, not add to the number. So, small little detail there. So, the general idea is that we choose a non-MPY subarray. So, from here, we could pick any contiguous subarray from these elements. Now, of the subarray that we choose, what we're going to do is choose the element in that subarray. So, right now, let's say my subarray is this 3 93. We want to choose the element in that subarray that has the highest prime score. Now, if multiple elements have the exact same prime score, then we choose the one that is most towards the left. So, these are the numbers. Let me draw the prime score of each of these numbers above it because the prime score is basically the number of distinct prime factors of a given integer. So now you can kind of see where the complexity of this problem is coming from. It's coming from the fact that we have like 10 different things to account for at the exact same time. But when you actually break down each thing, it's not crazy difficult. Putting them together is the difficult part. But anyway, so for a number like three, what are all the prime factors? Well, this is where things get a little bit mathematical. There's this concept of prime factorization. Like if you take a number, let's say I take a number 100 for example. I can keep factorizing it. I can say, okay, well, two factors of this number are 50 and two because if you multiply these two numbers together, then you get 100. Okay, I can't break down two any further. I guess I could. I could say, okay, I get one and two because if you multiply these two together, you get two. But that's going to go on forever. So this is like our base case because that's a prime number too. But we can take this number and break it down further. And eventually we might get to something like this. I'm going to say okay two and then 50. And we break 50 down. Maybe we do it to two and 25. And then with 25 we break it down into 5 * 5. So this is like the prime factorization of 100. For 300 they give us that example as well. Now with the prime factorization what is going to be the prime score of 100 in that case then? Well, you see four factors here. So you might think four, but no, we take the distinct prime factors like they say over here. So we see that we have two and we have five. So the prime score of 100 is going to be two. The prime score of 300 was three because it had these prime factors 2, three and five. Anyway, so now you get the idea of prime factorization. The prime score. So I believe three has a prime score of one because it's just a one and three. Three is itself a prime number. Nine is not a prime number. Nine can be broken up into three * 3 and thus the prime score of that is going to be two. Three over here again just has a prime score of one. Just assume that when we do implement the code of this uh solution that we will take every single number in the input and get the prime score of it. That's going to be kind of like the pre-processing. I think we're just going to do that up front because it's going to make our life a little bit easier. And the time complexity of that is going to be roughly n where n is the number of numbers in the input multiplied by the square root of n. That's a pretty easy part to do that. I can just show you in the code. So just assume that we have that. So now let's focus on the other aspects of this problem. So now this is my subarray I chose. I want to know which one of these numbers has the highest prime score. Nine has a prime score of two. So then we take that number and multiply our score by it. So if our score was initially one, we're going to take that number, not the prime score, but the number itself. Again, this is a minor detail that makes this problem very difficult to reason about because there's so many things going on. You have to remember we don't actually multiply the prime score even though we want like to choose the biggest prime score. Then we're going to take the number and then multiply our score by that. So our score then is going to end up being 1* 9 which is going to be nine. Now in terms of picking like what would be the biggest prime score, we could scan through it. We might end up using a data structure like a heap as well. But I think one observation we can make from this is that since we are trying to maximize our score, ideally we'd like to pick the biggest number from our subarray. We'd like to pick the nine of course cuz that's going to end up maximizing our score. Now it just happened to be that nine had a prime score of two. But it's not always going to be true that the biggest number has the highest prime score cuz I think if we had the number 11, it has a prime score of one as well because it's a prime number. But it is not the biggest prime score. This number which is smaller than 11 has a bigger prime score. So again, multiple things to keep track of at the same time. Okay. So now with all of that said, what should we do? How do we go about solving a problem like this? maybe even in the most brute force way. Well, I'll show you that the brute force solution is actually not super crazy cuz it's just going to be a greedy solution. Like we kind of observed, we'd like to pick the biggest numbers to maximize our score. We only have at most K operations. So, this is what I thought of because when I take a look at a subarray like this, I say that to maximize my score, I want the biggest number. It looks like the biggest number is nine. Now the question is how many subarrays exist in the input such that nine has the biggest prime score because that tells us how many times we can take our score and multiply it by nine. We know there's going to be at least one subarray because the number itself is a subarray and then thus it must have the highest score. But how far can we go to the right and how far can we go to the left? So this is going to be sort of like a leak code medium. This problem is basically like five or six different leak code mediums combined. This is kind of my intuition here. First of all, even though we know that nine itself is a valid subarray, we're only allowed to choose the same subarray a single time. We can't repeatedly choose the exact same subarray. But now we might say something like this. Okay, this is one subarray. Okay, well maybe this is another subarray including nine. And this is another subarray including nine. Now our question is going to be in this subarray does nine have the biggest score? Well yes actually it does. And what about this subarray over here? Does nine have the biggest score? Actually yes it does because nine has a score of two. I believe eight is just two cubed. So the only prime factor it has is two. So that's a single prime factor. So it looks like so far I've counted three subarrays with nine. And the problem is I only went looking to the right. I also have to look to the left as well. So then I might find this subarray over here. Uh this one and this one is also valid and this one is also valid as well. So now you might think, okay, so there's only five subarrays, right? Like these three that I've drawn and then these two as well. That's actually not the case because what if I start here and end over here? I didn't include that subarray. What if I start here and end over here? I didn't include that subarray either. Same thing with this. If I start here, I can end over here and I can end over here. The easiest way to do this rather than like brute forcing it is just to figure out from nine kind of like a two-pointer method like you go as far left as you can. So I find that okay I can go over here this number does not have a bigger score than nine and I can go over here. So I can go this far left and to the right I can go this far right cuz you know we reach the ends of the array. So this is how I think of it. Like I have my starting or my left value and I have my right. And when I say this, I really mean the indexes, right? My left index and my right index because that's what defines a subarray in the first place. It looks like I have three choices for my left subarray. I can start here or I can start here or I can start here. So I have three choices for the left boundary of my subarray and I have three choices for the right boundary. I can be here, here or here. So three. Guess what I'm going to do? I'm just going to take three times three and then I'm gonna get nine. So there's nine different subarrays that we could create including this number. Now if you don't believe me, let me again just give you a little bit of the intuition of that. This is one starting position. And then I could end here or I could end over here. That's two sub rays. Or I could end over here. That's three subarrays. When I'm starting over here, I could end over uh here. Or I could end over here. Or I could end over there. That's three more. When I'm starting over here, I could end over here, here, or here. That's three more. So, I counted nine total. So, it makes sense. Now, how are we going to get this three and this three? Well, you could kind of just take the indexes. So, if I had 0 1 2 3 4, I can just take this minus that plus one. Same thing over here. This minus that plus one. That'll give me like this distance and it'll give me this distance. Okay. Now, why did I go through all of that logic? Well, now we pretty much have a brute force solution. Let me tell you what the brute force solution would be at a high level. This is what we would do. We would get the max value from our nums. So how am I going to do that? Probably by using a heap because then we can do it in log time. How many times would we do it? Probably roughly like in the worst case k log n because what I'm going to do is take the max number. Okay, I get the max number. It's nine. I want to know how many subarrays are there including nine. Well, there's nine subarrays. Well, we only need two of them. Our K count count is two. So, I'm not going to use all nine of them. I'm going to say, okay, well, we're going to take two of those. So, I'm going to take the max number, which is nine. And then I'm going to update the score. Well, I'm going to update both. I'm going to update the score, and I'm going to update K, which is kind of the count. By doing that, I'm going to say, okay, we want to choose nine two times. So, I'm going to say 9 to the power of two. If we chose it like five times, we would do 9 to the power of five. And then we would take that and multiply it by our existing score which let's say was 1 initially and in this case we're doing squared. So 1 * 9 squar and then we end up with a total of 81. So this example is pretty simple but imagine if this was like 20 for example or maybe even just 10. So just to continue with this example if this was 10 I would say okay well now my score is going to be 1 * 9 to the power of 9. Now my K, initially it was 10, but now I'm going to set it to be one because we used nine different numbers. So now I'm gonna say what is the second biggest number in the input and I'm going to again just get that from my heap. It's going to be eight. So suppose now I got eight and then I would count how many subarrays are there where eight has the highest score and it is like the leftmost element. So I mean I think there's one and then there's two subarrays because if I go here that subarray is not valid. nine has a bigger score. So there's two subarrays and that's enough because right now our K count count is one. So we would say multiply this by K to the power of one. Even though we have two subarrays, we don't need two of them. We only need one of them. So that's where this comes from. And then at this point, we would stop. Now there's nothing wrong with the solution I just mentioned to you. The problem comes from the fact that for each number whether it's nine or eight or something else for us to know how many to count the number of subarrays where it is the number with the max score that two-pointer method I talked about where you kind of take the pointer and go that way and the pointer and go that way. In the worst case that's going to be an O of N time operation. In the worst case I think we're doing like K operation. So I think the time complexity turns out to be k * n plus the prime factorization stuff that we're going to do which I think is going to be n * the square root of n. But actually this should actually be a different variable. Let's say m because it actually represents the value not uh the number of values that we have. So I'll analyze this more when we get into the code. But this is going to be the time complexity of the brute force solution. This plus this term over here. But there is a little thing that we can do to optimize this part and that's going to involve something that typically is a medium or a hard leak code problem involving something called the monotonic stack problem. So again that's why this problem is so difficult. There's like 50 different things going on and if you want to solve it optimally you have to make a lot of observations and optimize every little thing. So once we do the monotonic stack um optimization the bottleneck is just going to be pushing and popping from the heap which I believe is going to be uh this term down here and then this will actually change to be k * log n. So that will be the overall time complexity. Okay. So now let me get into the monotonic stack part. And I will say that since we already talked about so many different things, if this next part is difficult for you, there is a leak code medium that is basically going to explain the stuff that I'm just about to talk about, let me show you which problem that is. If you head over to a neat code.io and I think if you go to the neat code all list and you search for a greater, there is a problem called the next greater element. I think there's multiple variations of this problem. There are some follow-ups, but this is a leak code easy. And the uh solution, which is the stack solution, involves a monotonic stack, but I would say that this uh solution is definitely a medium caliber problem. So, if you're not familiar with monotonic stack, definitely check this thing out. It's free. Um, but now to get into it, I feel like this video is going to be plenty long, so I'm just going to kind of show you what I'm talking about. Imagine if we took a array that was given to us and then we converted it to the scores. And let's say the scores looked something like this. I have five, four, three, and then maybe five, and a seven, and then seven, and then a two. I'm just putting some random numbers here. Ultimately, what we're trying to do with the scores is for each given number is get the left and right boundary of it. So, I'm going to have my left and right arrays. So, this is where the pre-processing comes in. And I'm going to initialize this left array somewhat intelligently. Same thing with the right array. Initially, I'm going to say like for for a number like this one, what we want to know is like how far left can we go where this number is the biggest score. And if we were able to say that like this number is bigger than everything on the left side. So in other words, like this is kind of the boundary, we're going to actually put a negative one there to indicate that everything is available to us. If we had like zero here, so this number which technically is the correct one in this case, that zero indicates that we stop before the zero. So we say that's the boundary. I can go all the way up until that zero. So those are the semantics I'm going to use for this. And you'll see why when we actually code it up, it makes the code trivial. And so similarly, when I go all the way to the right, I'm going to indicate that by taking this index that is technically out of bounds, which is equal to the length of the input. And that's what I would put over here. It'll make more sense once I just probably dry run through this and especially when I code it up. But initially to indicate that we don't know the boundaries of these, I'm going to put a negative one everywhere. And for the other ones over here, I'm going to put n where let's say n is like the length of this, which in this case is seven. So I'll just go ahead and put seven for all of these. So now the way this is going to work is we're going to have a stack. Off the top of my head, I actually don't know if this is going to be monotonic increasing or if it's going to be monotonic decreasing. But let's just reason about it for a second. Let's look at this and let's see what would happen. I have a five. I'm going to scan through all of these. I'm going to push the five to my stack. So, I have five. Great. And for five, by the way, it makes sense that negative one is the left value because I mean, we can't really go any further from here. But now I get to four. Now I see that four is smaller than five. So this score is smaller than the previous one. So what does that tell me? That tells me I already know the left boundary for this element. It's going to be the previous index. And by the way, when I actually code this up, I'm not going to be pushing the values onto the stack. I'm actually going to be pushing the indexes. I'm just not drawing it that way because I feel like that would make it even harder to reason about like as you're watching me do this. So that's why I'm pushing the values. But know that in the code I'm going to push the indexes. So anyway, so now I see that four. Okay, I already know the left boundary for four. Now it's the previous index, which is zero. So I'm going to update this index and I'm going to set it to zero. So uh let's just put like a zero over there. Now I don't quite know the right boundary of four, and I definitely don't know the right boundary of five either. So I'm just going to go ahead and take four and push it to the stack as well. Now I already know that this is going to be a monotonic decreasing stack just by going through this example. But I'm going to continue this dry run now. So now I'm going to see another number three. Okay, so three is smaller than the previous number. So that means I know the left boundary for this now it's the previous index which was one. So for this position I'm going to put a positive one. So one and then I'm going to push three to the stack as well because we don't know the right boundary for this. Now things are going to get interesting. Now I see a five. Five is bigger than the previous number. So I don't know what the left boundary for five is. But I definitely know that this number that's on the top of the stack, its right boundary is going to be me. And I'm at index three right now. So I'm going to pop this guy. And I'm going to then say I'm going to update the right boundary for that uh element. And I'm going to set it to be three because that's the index that I'm at because for three, this is the boundary. Three is the biggest score in this interval. So we see that the left boundary is one, the right boundary is three. And so we take everything in between that. In terms of the code, it'll probably be something like taking this index, which I think is two, subtracting one from it. That tells us how many choices we have for the left value. and also taking this subtracting two from it which tells us how many choices we have on the right side. So that'll be one and one respectively and then we'll take one multiply it by one which will get one in the output that tells us there's only one subarray that has three as the biggest score. So uh anyways continuing with that now we're not just going to pop a single time actually we see that four is also less than five so pop four as well. So now I can say for this four I know your right boundary too it's also going to be three. So I go ahead and just put a little three over here. And this is the edge case. This is what makes this problem a hard problem. Now I have five and I have five on the top of my stack. There's a tie. What do we do? Well, the problem statement told us that if there's a tie, like if we were to choose this subarray over here, we would say that this five is the biggest score, not this one. So what should we do? Well, I see that. Okay, I'm equal to you. So, I say actually for this five, I found the left boundary for my five. I didn't find the right boundary for this five. I found the left boundary for this five over here. So, I will not pop this five over here. And I will update the left boundary over here now to be uh the index that this value showed up at, which is zero. So, I'm going to put a zero over here. I don't quite know the right boundary of this five, so I'm going to push it to the stack. Okay, now I'll try to quickly go through the rest of this. We have a seven over here. It's bigger than the top of the stack. So, we can now pop this from the top of the stack. And we would pop this as well. So, we say for these two fives, we just found the right boundary. It's going to be this seven. And the index of that, I think, is four. So, we will update uh this to a four and this to a four as well. And that makes sense because from here we can tell that every subarray over here this is going to be the biggest score. And for this five we can say that this and this every subarray in here this is going to be the biggest score. And then seven is going to be pushed to the stack. And then I'm going to push the second seven. Well, we're going to visit the second seven. And we're going to see that. Okay. For this guy, I found my left boundary. It's also going to be four. So over here I can put a little four. Didn't find the right boundary for this guy, though. So, I'm going to go ahead and push seven to the stack. Now, I found a two. Two is smaller than the previous number. So, I found the left boundary for two, which was at index five, I think. So, I'm just going to change this to a five. And then I think two is going to be pushed to the stack as well. And then we're done. So, this is the pre-processing that we did. And you see we accomplished exactly what we wanted to. And we did it in linear time. Each element is going to be pushed and popped to the stack at most once. And we might actually end up with some elements remaining on the stack. The elements that are remaining on the stack for all of those, we would want to say that we never found a right boundary for them. So we can assume that the right boundary is just going to be the end of the array. And that's exactly why I initialized the array this way in the first place. And also at the same time for some elements like this and this, we never found a left boundary. So we can assume that we can just go as far left as possible. That's why I initialize this with negative 1 and this with negative 1 as well. So let me just pick any arbitrary number. Let's uh pick this seven. So seven it tells me that its left boundary is negative 1 and its right boundary is seven. This seven shows up at index 0 1 2 3 4. So I can say that on the right side I have how many choices? Well, it's going to be seven minus four choices for my right uh boundary. So, meaning I could have this or this or this as my right boundary of my subarray. Now, for the left side, I can say four minus the left value, which is going to end up being four plus one, which is going to be five. That tells me there's five different positions. That could be my left boundary. This is one of them. This is a second one. third one, fourth one, and fifth one. So I have five on my left side and I have three on my right side. I can take five, multiply it by three. There are 15 different subarrays where this seven is the biggest element. And you might think, well, okay, like this subarray, for example, there's two sevens. That's fine because when there's a tie, we take the leftmost element. Okay, that sounds pretty good. But what about this guy? How many subarrays for this seven are there? It shows up at index 5. Well, we can take 7 minus 5, which gives us two. There are two choices for the right boundary. This and this. How many choices are there for the left boundary? Well, we can take five minus 4. There's only one choice for the left boundary, and that is this itself. Because if we go any further to the left, we encounter this seven, which is a tie with this. But when there's a tie, we choose the leftmost. So this would not be the biggest score in a subarray like this one. So there's only two subarrays with this guy. This one and this one because uh we got 1 * 2 and that gave us two. But anyway, so this is more or less all of the intuition I think to solve this problem. I think the heap stuff would be more easy to cover in the code itself. So let's do that. So I know somebody's going to comment saying that this problem was really really hard and maybe even after watching this video you still don't understand it. And that's fine because to be honest, for me, this was also insanely difficult. But I will also say that if this problem really was that hard for you, why are you trying to solve it in the first place? Why don't you go solve a slightly easier problem, like a slightly easier monotonic uh stack problem? I promise it'll make your life easier. You shouldn't jump straight into really, really crazy problems like this one. Okay, finally, to start coding it up, I'm going to get the length of the input. I usually don't do this, but we're going to need this a lot. I'm also going to get the mod because our result could be really big. They want us to mod it by this prime number. And I'm going to initialize my results or my score with one. Now, first I'm going to convert the input numbers into their prime scores. That's actually pretty easy. We're going to go through every number in the input. We'll initially say the score of this number is zero. And then we're going to just go through every single possible number that could be a factor of n. So we're going to go through every number. Let's say for f in range from two up until the square root of n. The way Python does this though. So I'm going to take the square root of a number n that could be a decimal. So we'll convert it into an integer. This will round it down though. And also Python is non-inclusive with the second value in the range. So I'm going to add a plus one here. Now why are we only going up until the square root? Well, if you take for example a number like 81. Well, I think we talked about it in other videos, so I won't go super in-depth. I think a better example would be something like 153. You might think, well, three is a prime factor of this. And well, what's going to happen in this code is we're then going to divide this number by three, and then we're going to be left with another number. And that number could either be non-prime, in which case we will find the factors of that, and the factors won't be any larger than the square root of the previous number that we started with, or that number itself will be prime, in which case we're actually going to count that at the end. So at the end if the number that's left over isn't a one. So if that number if let's say um n is greater than or equal to two then we are going to increment our result by or sorry we're going to increment the score of it by one and then after that we will um say prime scores append this score. But the general algorithm of this is what's most important here. So here what we're going to do is for every f we're going to check is f a factor of n. So if n moded by f is equal to zero, there's no remainder. That means it's a factor. Well, then we're going to increment the score here. Add to this. And then we're going to basically divide n by f. But like we saw in the drawing explanation, a single prime factor might show up multiple times for the same number. So we have to actually do this as a loop. So while n modded by f is equal to zero, go ahead and do this. So this is just integer division. Okay, so this wasn't really the crazy hard part of this problem. This was just phase one. Phase two is going to be the monotonic stack part. And I'll copy and paste some of the variables. This is just the left and right boundary arrays I was showing in the drawing explanation. And this is our stack, which is going to be monotonic decreasing. Then I'm going to go through the input. Well, not the input, the prime scores because that's what we care about, not the numbers. I'm going to enumerate them so I get the index and the score at the same time. And the first thing I'm going to do is check while my stack is non-MP and the prime scores the top of the stack. To get the top of the stack, actually, let me redo this. I'm going to get the top of the stack like this in Python. So, this gives me the index. That's what this is going to be storing. And now I want the actual score itself. So that's easy to just look up in the prime scores array. And if the prime scores array, or rather the top of our stack is actually less than my current score that I'm looking at, my current S, well that means I just found the right boundary for the top of the stack because my score is bigger and the first bigger score is what we want. So then what I'm going to do is do stack.pop. That's going to give me the index. And then I'm going to say, okay, well, for that prime score, which is at this index, I found the right boundary of it. So, right bound of this index is going to be the current index that we're at, I. So, I'm just going to put an I there. And this loop might execute multiple times. Now, what if they were equal? Would we still want to execute this loop? No, because if they're equal, this is not the right boundary. We can possibly keep extending it. Now before we can do this, before we can say stack.append the current index, we do have to do another check for the left bound. Maybe for the current score, I found the left bound of it. How do I know? Well, if my stack is non-MPT, that must mean that the value on the stack is either bigger than my current score or equal to my current score. Either way, that must be the left bound of the current value. So I say left bound of I is going to be the top of the stack which is at index negative1. By the way, if you don't know like these little Python tips and tricks, highly recommend checking out my Python for coding interviews course on neat code.io. I really think Python makes your life a lot easier with really difficult problems like this. But anyway, so this was phase two of the algorithm doing the pre-processing so that now for any given element, we can count how many subarrays we can create where it will be the maximal score element. And now is going to be the heap part. So I'm going to create a min heap. I'm going to use list comprehension from Python where I'm going to go through every index number and then I'm going to use enumerate to unpack those from the input nums. And our heap, we want it to be a minimum heap. Or rather, we want it actually to be a maximal heap because we want to be greedy. We want to pick the biggest elements from the nums array. But Python doesn't have max heaps. So we get around that by taking every number and making it negative. But when we pop from the heap, which we're going to do like this, heap pop, we can expect that we will get the number and the index. Whoops. And then we're going to set the number to be negative which will undo what we did over here. So just to make some notes, we're pushing the number and index on the heap. Now this is just an array initially. To turn it into a heap, we do heap of fi on it which runs in linear time I believe. And now we can finally do some looping. So I'm going to say while my k is greater than zero, we have some operations to perform. And the operation we're going to do is first of all just heap pop from the min heap. So let's get the score of the current number as well because that's why we created the scores array in the first place. So I'll say score is equal to prime scores of this index. Okay. Now I want the left and right boundaries which again aren't super difficult to get. It's just a matter of doing this left bound of the index and right bound of the index. But what I really want is a left and right counts because these left and right boundaries can give me that. So I want the left count. How many different positions can we have the left pointer be? And that's just a matter of taking the current index subtracting the left bound. And for right count, I can get uh the right bound and subtract from it the current index. And so now if I want the count of how many operations we can do, it's just going to be left count times right count. Now it's possible that this count is actually greater than our current K value. Maybe we don't even need to do this many operations. For that reason, I'm going to do this. I'm going to say operations is actually equal to the minimum of the count as well as K. And then after that, we can update K, subtract from it this number of operations. But don't forget to actually update the result as well. The result will be this itself multiplied by the current number that we just got. And remember the whole point of doing all of this was to say that this number can be chosen this many times. So we're going to take that number itself and raise it to a power. In Python we can do that like this. N raised to the power of operations. And if it becomes really big, we want to mod it by the third parameter which we pass in is mod. And then multiplying the result by this could also be too big. So let's mod that as well. So again, so many different things going on. I guess I could have shown you how to implement this function from scratch. But I mean, I really think in an interview this is already way too much. I feel like this problem, even for someone who's good, would take a long time. But anyways, I think this is the entire code. And then after everything is done, we can just return the result. So, zooming out a bit so you can see everything. And over here on the left, you can see it does work and it is pretty efficient. This video, I'm not going to lie, took me a long time. If you found it helpful, please let me know. Like, subscribe. Thanks for watching. Check out necode.io for more. I'll see you soon.