Defuse the Bomb - Leetcode 1652 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem diffuse the bomb the idea is we're given an input array of integers and we're given another parameter K and this example let's say it's three so K is the magic number for this problem if K is zero we're going to replace everything in this array with zero when they say replace they don't necessarily mean doing it in place with the array I'm pretty sure you actually have to create create a separate array so that's what we're going to do we're going to put the new values in a separate array so if K is zero we can just return all zeros and the length is the same as this so that's pretty straightforward the other two cases are a bit more interesting if K is a positive number we're going to do this for every number we're going to create a window of size K because we want to replace the I element with the next K elements so basically a window of size K in this case and get the sum of that window in this case 7 + 1 + 4 I think that's 12 and so we take 12 and then place it over here in the second array so we'll have a 12 over here and we'll keep going we want to do the same thing for this element so get the next three elements 1 2 now we ran out of elements there's nothing left so one tricky thing about this problem is this array is considered circular I'll show you a really nice trick to deal with circular arrays so what we actually want to do is get these two elements and then the next element which is technically out of bounds but what we would actually want is for that element to have been considered to be over here and so then we get the sum of all these that's 10 we put it over here and we can keep going just like this so we' do the same thing with this that'd be looks like 16 and for this one it would be 13 so that's if K is positive K can actually also be negative so what if we had K is equal to -3 well then for each element we want to do the opposite we want to get the previous K elements and again since the array is circular we'll go around here 1 2 3 and so once again we will get a 12 in the output over here for this element we'll do the previous three so essentially we're taking the absolute value of K and we're getting a window of that size so this sort of very Brute Force approach that I'm showing you clearly the time complexity is going to be o of n because we have to fill in every single value and to fill in a particular value we have to iterate let's say k times for that window and so this Brute Force solution is going to be n * K I think it's worth coding up this solution so I'll quickly do that but before I do let me show you that trick that I promised so the trick here is actually very simple once you know it it's going to make your life so much easier think of this we we get out of bounds sometimes right and those out of bounds indexes are going to be four five up until 6 let's assume that K is equal to 3 in this case or it could also be equal to -3 either way we're going to take K spots here because we might end up out of bounds like for example if we're here give me the next K if I'm here give me the next three if I'm here next three here next three Etc so that's why I'm only putting three elements here and the cool thing is you actually don't need to create more elements you don't actually need to create a bigger array you can do modding to like assume these positions kind of exist like implicitly exist so I'm going to draw them like in Gray but assume these elements are actually like let's say these first three we get five 7 and 1 so when we do our pointer stuff like let's say my ey pointer is over here and I want the next three elements I'll do a nested Loop to do that I'll have my J pointer iterate over this portion and it works when my ey pointer is here though if I have my J go through this portion I end up out of bounds but I wish that index 4 corresponded to the element five because that would make it circular and the way to do that is to take each pointer and mod it by the length of the array which let's say is n and n is four in this case when you do that if my JP pointer was over here at index 4 and I take it and I mod it by four I'm I'm going to get zero so that's going to tell me my JP pointer isn't actually at four it's actually at zero so if a pointer gets out of bounds it will automatically be corrected that's the advantage of this approach and it actually works uh going the other way as well if we were looking at the previous K elements because I'm going to do this I'm going to have let's say my window and I'm going to populate this guy great I'm going to have my window populate this guy which is actually populating index zero I'm going to have my window and I'm going to populate uh this guy which is actually populating this index now you have a bit of the intuition let me show you the code I'm going to create my result array I'm going to make it all zeros of the size of the input and I'm actually going to save that in a variable because I think we're going to need it a few times and next I'm going to go for I in range n for every position I want to populate this position for that I need to know if K is greater than zero we're going to do something else if K is less than zero we'll do it differently and if K is equal to Z we don't need to do anything we could actually have an if statement here if K is equal to zero just return the result and then we don't even need to handle it here this is kind of a small optimization it doesn't really make a big difference our code below will actually handle this case anyway so it's a little bit unnecessary but we will I guess iterate n times which is somewhat way wasteful but not a big deal anyways here if K is greater than zero we want the next K element so I'm going to say for J starting at I + 1 going up until I + 1 + K this plus K is kind of the offet here with python this is non-inclusive so that's why we still have that plus one and so for this we want to compute the sum of all of these elements and then replace result at index I with that value so we might as well just add the values to this position because it's initialized as zero anyway we can do something similar down here but we want to go in reverse order for J in range I -1 up until I -1 - K going in reverse order there's one little bug with this K could be negative in fact it is negative if this is executing it's positive if this is executing so the plus K is fine but us K should be minus the absolute value of K and honestly I think they could have done a better job in the problem description here where they say replace it with the sum of the previous K elements they could have said the absolute value of K but anyways and in here we'll do pretty much the same thing result of I add to it code of index J and then at the end we return the result now this looks pretty straightforward and that's because there's a small issue here I'm not doing the modding that I talked about my JP pointer could end up out of bounds it's definitely going to end up out of bounds in both of these cases so what should I do well we can just take it and mod it by n and same thing over here so that's the code let's run it and you can see that it works but this is not the most optimal solution I don't think you will pass in an interview with this solution but I guess it depends on the interviewer the company and a bunch of other factors now how do we go about optimizing this well once you know the trick and if you've heard of the pattern called sliding window it's not too difficult if you haven't heard of this pattern you can consider heading to n code iio if you go to the sliding window pattern there's a bunch of problems here and you can also check out the courses which will teach you these things like from scratch got videos practice problems code animations articles all that stuff but anyways back to the sliding window what is it it's pretty simple whether our K is positive or negative we want to take like the absolute value of K and get Windows of that size we already kind of know that much so the algorithm will work like this we have two pointers a left and right pointer initially we'll just start at the beginning and then keep summing up until our window is of size K and once this is of size K we will say if our K is positive we want to take like this window and say that the sum belongs to the previous element in other words we want the next K elements to fill in this element but what is this element it's out of bounds it's actually this element over there so the modding will actually handle this even if it's like a negative index at least uh that's true in Python it actually won't work as expected in other languages like if you have a negative number and you are modding that negative number if you're doing this in other languages the easy way to get around that is to make the number non- negative and to not change the mod since like I have some number X and I'm modding it by n if I add n to this value that's not going to change the mod obviously right if I say like I have 11 modded by five I'm going to get one as the remainder if I add five to 11 I get 16 modded by five and that doesn't change the remainder at all so that's what you can do to one of the indexes if it could potentially be negative but anyways uh this trick will work and so like with the sliding window approach we can do that so in this case with our window we want this window to be filling in the value for left minus one if K is positive if K was negative we'd be wanting this window to fill in r+ one meaning this position and we can just have a couple if statements to handle that and then we can shift our window the optimization comes from the fact that when we shift the window we will uh shift like our right pointer here adding this to the current sum and we will shift our left pointer over here removing this from the current sum so this current sum might populate this or it might populate the value ahead of it and if the value ahead of it is out of bounds that will be brought back into bounds with the mod that we are doing doing it this way our window will shift only one time each like potentially up until the end of the entire input plus K like this distance over here so time complexity is going to be linear let's code this up so I'll leave some of this boiler plate here so here I'm going to change this first Loop to n + K and I'm going to change this to R and I'm going to have a left variable which is zero and I'm going to have a current sum which I'll initialize to zero so what we're going to be doing here is every single time we want to add the current number to the current sum so code at index R now index R could be at of bounds so don't forget to do the modding there's a couple of cases we need to handle either our window is too big or it's exactly the right size and maybe even both of them so if the window is too big we can get the window like this right minus left + one that's the length is it greater than K because if this is the case we want to shift the left pointer if we shift the left pointer we have to make sure that we do the modding like this oh whoops that's not mod and with the current sum before we shift the left pointer let's let's take the value that was originally there and subtract it from the current sum so this and here again don't forget to do the modding there's actually a small bug here what if K was negative well we want to compare the length of the window to the absolute value of K in that case cuz they don't mention it in the problem description but that's what we want to do so that's if the window is too big we will correct it we don't have a loop here because our Windows starts at a size of zero so it'll never exceed the size of K by more than one and down here we will check if we're exactly the right size if right minus left + 1 is exactly uh what we want it to be which is going to be K the absolute value of K as we learned then we have two choices well two different cases to handle if K is greater than zero or otherwise if K is less than Zer well what if K is exactly equal to zero well in that case we don't really need to do anything we can just leave the array as and return it so that will work even though we could add an if statement up above so here if K is greater than zero we want to update the value in the result array at left minus one but again this could be out of bounds let's mod it by n and that will be set to the current sum and we'll do something similar down here except making it right + one there you go I think the hardest thing about this problem is probably just dealing with like the circular array Parts the fact that you have to Absol value K and if you're new to the sliding window I think this would probably be challenging as well especially if you're using non-python languages you'll have to like add a plus n here and maybe a few other places and whoops I realized that this plus K also should have had an absolute value around it kind of shows you how easy it is to mess up but now you can see that this code works it's pretty efficient if you found this helpful definitely check out n cod. for a lot more thanks for watching and I'll see you soon