Final Array State After K Multiplication Operations I - Leetcode 3264 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem final array state after K multiplication operations one the idea is pretty simple we're given an array of numbers we're also given an integer k k is five in this case so we want to perform five operations for each operation it's pretty much already pred decided like we don't have a choice of which operation to do we are always going to pick the minimum element from the array of elements and then we're going to multiply it by the multiplier which in this case is two so we're going to double this number and then it'll be replaced with a two so you can see that after one operation the new array looks like this we have a two over here now next we're going to do the same thing get the minimum among these now we actually have two minimums so there's a tie so we will just pick the leftmost two and then double it so we'll get a four in that spot once again the minimum element is going to be a two it's going to be this one we double it get four just keep going like that until you end up with this array we're not trying to minimize or maximize anything we just return the final array so it seems like there's not a lot of room for creativity in this problem so we just mainly need to figure out what is the fastest way to do the simulation in the worst case I mean Brute Force we can just take the input array whether you want to create a copy of it or not I guess it's up to you you probably could modify the input if you want to but generally that's not recommended so we'll create a new array and then just doing a simulation on that for every operation in the worst case we might have to scan through the entire input array because we might end up changing the same element multiple times like maybe all of these numbers are really really big and we have a one over here we might end up scanning through that portion of the array multiple times to do the operation on the same element multiple times so in the worst case time complexity is going to be o of n like scanning through the entire thing we have to do that K * it'll be n * K in the worst case and the bottleneck from doing that if you actually think about what's going on in The Brute Force what are we doing we're having to iterate over the entire input array to potentially get what the minimum element is before we can do the operation on it and that is the linear time part of this code now you might think that maybe there's a clever solution to this problem well first of all given that this is an easy problem there probably isn't going to be a super clever greedy algorithm to this one at least that wouldn't be like the suggested approach but there's a pretty easy optimization we can make to this with a data structure that you've hopefully heard of it's called a heap if you haven't heard of it there are plenty of resources on N code. which will teach you all about heaps there's plenty of animations practice problems all that stuff but you pretty much have to know what the STA structure is because basically it will optimize the get min for us it'll take it from being a linear time operation to actually being a log time operation so this is how it's it's going to work we basically throw all of these numbers into a data structure called A Min Heap and from that Min Heap we will be able to get the minimum in log end time so right now our Heap will look like this 1 2 3 five and six we're going to get the minimum which is one and then we're going to double it and then we're going to add it back to the Heap so we'll add a two back now the Heap pushing and popping from it it's going to be login time operation but we guarantee that they will still be sorted in some sense since this is a heap and we kind of just keep going like that so we get the metum once again it's going to be A2 I get rid of it and then read the double of it so we get a four here and we kind of just keep going like that of course every time we update a value in the Heap we also update it in the input array so we' get an update something like this um maybe this one became four and this one became two I guess we could have also left this as a two and made this one as a four not that it really matters well actually now that I think of it of course it does matter because in the case that there is a tie we want to pick the leftmost element okay so how can we do that with the Heap because if we only add the elements to the Heap like the numbers themselves then we kind of lose the index when you pop an element like two how do you know which index it goes at well in many languages you can Implement like a custom comparator so what you would do is instead of adding the elements themselves each of them has a unique index 0 1 2 3 Etc you'd add the indices to the Heap and then for the comparator rather than using the indices which would give us like this as the minimum this is the second minimum Etc we would use a custom comparator where we map that index I to the actual number it represents and then the Heap logic would be implemented with that python actually makes it easier for us though we can just add a tuple a pair of elements the first element will be the element itself n cuz we want to use that for the Precedence but if there is a tie then we want to use the index I so smaller indexes will win so this is the pair of elements that we will be adding to the Heap so for example this three over here it would actually look like well the element is three the index is two so this is what that element would look like so this allows us to solve the problem more efficiently we will get the time complexity down to be K Times log n rather than times n so now let's code this up so the first thing I'm going to do is actually just create a copy of the input array nums so nums there's many ways to do this in Python I will do the double colon this time and this is what we want to return when we are finished first thing we want to do is build the Heap I'm going to use something called list comprehension in Python so I'm going to say for i n in enumerate and we're going to numerate the list of num and then here we're going to have the pair n i it has to be in this order that's important I know this line looks kind of magical there's many things going on here I won't explain every little detail about it but this is called list comprehension this is a tuple this is a numerate you can learn all these things in my python for coding interviews course it teaches you all these tips and tricks right now this is actually not a heap it's just an array of tupal to make sure that it has the sorted property of a heap we're going to do Heap q. Heap uh if5 on this array it'll basically make sure that this is actually in the form of a heap in linear time okay now we want to run the simulation so do the operation K time so let's say for underscore in range K and then we want to pop from the Heap Heap q. Heap pop Min Heap and we get the pair n i now there's two things we want to do first we want to double the element well not necessarily double it I guess just multiply it by this multiplier that we are given as a parameter so we want to take the element at index I so result at index I and originally um it has a certain value here we can just take that value and multiply it by the multiplier we could have also set it to n times the multiplier but I don't think it makes any difference we also want to make sure we add the new value to the Heap so Heap Q Heap push to the in Heap this same pair which is um well the value itself is result at index I and the index is I so I think we're good let's give this a run for some reason I had a plural and S here that's my bad okay now you can see that it works and it's pretty efficient if you found this helpful definitely check out NE code. this is the python for coding interviews course I was talking about by the way thanks for watching I'll see you soon