Image Smoother - Leetcode 661 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem image smoother we're given a two-dimensional grid that can be a variable size and we just want to apply a pretty simple algorithm to every single cell in this grid so for example this cell over here s we want to replace it with the average of the nine closest cells to it so like the 3X3 square around this position basically we would take 1 + 2 + 3 + 6 7 8 + 11 12 and 13 add all of those together and then divide the result by 9 because there were nine elements so to take the average we divide by nine and we want to round down in this case so if it's a decimal value we are going to round that value down now of course not every single cell is is going to have a 3X3 square like for example this corner over here if we were to look at the closest cells to it some of them happen to be out of bounds for those we pretty much ignore them but we take the average pretty much in the same way so with these existing cells we take all four of them add them together this time though we would not divide by nine we're not taking the average of nine elements we're taking the average of four so we divide that by four and we still round down and that new value that we have we would end up putting it in this corner spot conceptually this problem isn't super difficult in terms of code how exactly are we going to implement it because if we try to implement it in place like if I were to first look at this cell and then replace it with like the average of the values and I do that then I want to do the same thing here I want to replace it with the average of the closest values to it if we try to do that we're going to end up looking at the value over here it's not the same value that it originally was it's not going to be a one anymore so we're going to have a problem if we try to implement this in place at least if we do it in a naive way I will show you in the second half of the video that we actually can solve this problem in place but for now let's just create another copy of this grid and then fill that in as we solve this problem and then we'll end up returning that grid now the only hard part in my opinion at least for like a beginner would be for a cell like this one how do we even get all of the neighbors you could kind of hardcode it but that would take a lot of code the easiest way is actually to do a nested Loop like if this is the position that we're given and let's say the coordinates of it happen to be RC for row column we then would just run a nested for Loop starting from here going through this row then going through this row and then going through this row and that will allow us to accumulate all nine of those values and then we can divide that by nine and get the total how do we do that well if you look the top left corner is row -1 and column minus one the bottom right corner is row + one and column + one so we can kind of run a nested Loop where the row iterates over these values and the column colum iterates over these values one last thing to mention if we were to do that over here we would get some values that are out of bounds it would be easy for us to detect that a coordinate is out of bounds because we can verify like this is within the range of the size of this grid but one thing to notice is when we accumulate these four values we want to keep track that we only had four values because then we would end up dividing by four so that's just a little catch with all that said though we can code this up what do you think the time complexity is going to be well well one we're definitely going to have to iterate over this entire grid let's say the dimensions are n by m so we're going to have to do that and then for every single cell we're going to have to potentially iterate nine times now nine is a constant so it doesn't really change the overall Big O time complexity this would be overall time complexity and since we are creating another grid of the same size the memory complexity is going to be the same actually it's going to be n * m at least for the first solution we will find a way to optimize the space down to constant time but now let's code this up first with any type of 2D grid problem I just like to get the dimensions of the grid and that's pretty easy to do in this case just like this and then we want to create that two-dimensional grid that we're going to end up returning that copy and I'm going to initialize it with all zeros it doesn't really matter what you initialize it with in Python it's kind of weird to initialize a 2d grid so here with the first ARR we're going to multiply it by the number of columns cuz that's going to tell us how many values go inside of a row and then how many rows do we have that's going to be like this so This is called list comprehension in Python if you've never seen it before but basically gives us a two-dimensional grid of the size of this matrix it's all zeros and that's going to be what we end up returning but before we do that we actually do have to populate it so let's iterate over the entire input grid and we can do that like this now is the part where we are going to iterate over that 3x3 Square kind of centered around these coordinates so I'm going to use different variables for that I'm going to have I in range from like we said row minus one all the way up until row + one the only thing is with python this range function it will actually stop here but not include the last coordinate so if we want to iterate from here including this we have to actually set this to row + 2 we're going to do the same thing down here for J in range column minus one all the way up until column + one but it's not plus one it has to be a plus two and then what we're going to do is basically keep track of the total for now so I'm going to have a variable up here I'm going to call it total I'm initially going to set it to zero and for every cell so the image at these coordinates i j we're going to add that to the running total so far and we're also I'm going to keep track of the count so I'm going to have a second variable for count I'm going to increment it by one every single time but this code is not complete because right now what this would do is Count would always be set to nine because we're always going to iterate nine times well one thing we haven't done is validated the current coordinate to do that I'm going to go here and say if I is less than zero if it's out of bounds or if I is equal to the number of rows it's also out of bounds or if J is less than zero or if J is equal to the number of columns in any of those cases we've gone out of bounds then I'm just going to continue to the next iteration of the loop so that we don't ever even execute this part that way we don't update the total or update the count because if we tried updating the total of course that would get us an index out of bounds error now last thing after we've gone through that 3x3 Square we do have to take the total and calculate the average from it with the count and this is what we're going to set to the same coordinate the row column coordinate in the result not in the input Matrix but in the result Matrix and then that's what we're going to end up returning so let's run this to make sure that it works and as you can see on the left it does and it's pretty efficient it's about as efficient as as we can get in terms of runtime but the memory complexity can actually be improved even if it might not end up being reflected in elak code because the input size of this Matrix isn't super significant but the main reason we can actually do that is if you go here and read the fine print in the constraints you see that the value of an image is always going to be less than or equal to 255 and let me show you why that's important 255 is a special number because it's actually 2 to the power of 8 -1 why is that important well take note of this value eight that means in binary it's going to look like this four ones and everything before that is going to be a zero this is convenient because we only need eight bits to store this number okay well why does that help us well depending on the language you're using most integers are implemented I think has 32 bit integers in Python it's not entirely the case but in most languages you'll have at least 32 bits to work with so the original problem we had of why we had to allocate a new Matrix in the first place was we couldn't store the total like the average in a Cell because if we do that then if we wanted to calculate like the average of this guy he needs the average of all of its neighbors but if we overwrote those we can't get the original value back but if we have space here we can actually store the original value in the first eight bits like it's already there so we can leave those bits untouched but when we calculate the average for five for example uh let's take all these values and let's say I think it's 27 and then divide that by four it doesn't really matter what the value is I think it'll be something like six we can then take that new value that let's say is six and store it here in these bits so in a way we'll actually be having two values stored in every single position in the grid that works so then every time we want to calculate like the average of this position we can get the original value from the first eight bits which will allow us to calculate the average that's great and then by the time we want to return the entire resulting grid how do we do that because we know that we store the average here so when we do that we will have to for every single cell basically eliminate these eight bits or just take these and shift them to the right by eight bits that's exactly what we're going to do the only thing I haven't talked about is how are we going to take an arbitrary number and store it here and make sure that we don't touch these first eight bits well first of all we will take that number and shift it to the left by 8 Bits for example if we had a number that looks like this one01 in binary and then we take it and shift it to the left by 8 Bits that's basically saying we're going to have eight zeros that come after it so it'll look like this sorry if the handwriting is bad but then if we have that we can take this number and do an operation I think we can actually do either exclusive or or logic or because if we take this number and run exclusive or on it with this number what you're going to find is that these bits whatever they are whether it's a one here or a zero here they are going to stay as they are because we know that all of these are zeros they are not going to like conflict with anything here and we know that there's always going to be zeros over here because this number is only going to be up to 8 Bits large so with exclusive or will make sure that these values end up being placed here that's how we're going to handle pretty much most of the bit manipulation it all kind of centers around the fact that the max integer in any of these cells is going to be this which happens to fit within 8 Bits so knowing all of that we do not need to allocate an extra Matrix so we can reduce the time complexity from Big O of n down to constant space now let's code up this more optimal solution so I'm going to keep the existing code as is because then we don't have to like rewrite everything I'm going to get rid of this result Matrix and I'm going to rename the return value to image now let's focus on the lines of code that we are going to change so first of all we want to continue to compute the total among like those nine that 3x3 grid those nine cells we want to compute the total but we don't know for sure that this position that this cell has not been overwritten this might not be the original value that it was so what do we do with it we just want the first eight bits from this value we just want the original portion of that value how do we get that I guess that's the part that we didn't talk about but think about it when we have a number let's say we had eight bits like this 8 Bits And then we put any value over here it could be like a one1 or anything else this portion is always going to be greater than the number 255 because 255 is what this represents if we add anything past those first eight bits it's always going to be greater than 255 so in other words we want to eliminate everything before here so we want to take this and mod it by 2 56 that's another way of saying that we want to eliminate everything before these first eight bits so that's what we do to get the original value so that we can accumulate the total now with the total we are still going to divide it by the count to get the average of it but now we're not going to assign it to the result we're going to assign it to the image to keep it in place now remember this itself is not what we want to add to the image we actually want to take this and shift it to the left by so that's what we want to add here but for us to add it here we can't just do like the simple operation of plus we have to either use the logic or or logic xor I'm just going to do exor it really doesn't matter which one you use we can do it this way and I think logic or is like this so I'm going to keep it exor but that's pretty much it this is what we're doing we're taking that and storing it in the bits that go after the first eight bits so we're almost done now but but remember we can't just return the Matrix now because we're actually storing two values in each spot so if we only want the new value for each spot this is what we're going to do we're going to iterate over every cell in the output Matrix and for every cell we're going to make sure that we take that cell and shift the bits to the right by 8 that will get rid of the original value that's stored and make sure that we only return the new value which was the average that we ended up Computing so we're kind of in a way reversing the shift left that we did here we're shifting it to the right by 8 Bits this is the entire code let's go ahead and run it to make sure that it works and as you can see on the left yes it does it looks like the memory complexity isn't better at least according to leak code but that's really not the case and we know why because of like the way Big O works if you found this helpful please like And subscribe if you're preparing for coding interviews check out ncode IO thanks for watching and I'll see you soon