Increment Submatrices by One - Leetcode 2536 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem increment submatrices by one. So this is a pretty interesting problem. I guess you could say it is like a little bit mathematical. I'll try to go uh pretty quick because it's really just about like the trick and the math in this problem. So the idea is going to be that we're given a square matrix and we want to sort of perform uh these submatrix operations. So in this case, we're given a matrix of size 3x3. So n, of course, is going to be three. And initially, it's going to be all zeros. I'm not going to fill them in. Just assume that they're all zeros. And we're going to be given basically a submatrix for each query. So we're given like a list of submatrices. And that submatrix is going to be defined by the top left and the bottom right. So for the first one here, you can see we're given one one two two. So given that this matrix is zero index. So it's going to look like this. We're going to go to the first coordinate 1 one and we're also going to go to the bottom right coordinate 2. And so we say that this matrix has been uh incremented by one. This submatrix every position is going to be incremented by one. The next one we have is 0 0 and 1 one. So that's going to be over here and over here. So we can just go through everything and increment everything by one. So we get this and then we get a two like that. So that's exactly what we're trying to do. We're just trying to build this matrix and then return it. Now you can imagine this is a medium problem. They're probably going to want us to do more than just iterate over every single submatrix and do it like that. So that like in the theoretical worst case could be I think something like n^ 2 which is like the worst case for the size of a submatrix and that multiplied by the number of queries. So you could say it's q * n ^ 2. Now if we can do better than this it's probably going to be taking a shortcut which is not going to be doing the entire submatrix every single time. So maybe somehow we can just mark positions in our matrix to keep track of where we actually want to do the increment and stuff like that. So if that's the case, we could probably uh get the time complexity down to something like Q. We are going to have to iterate over every single query. Plus maybe we'll just have to iterate over the entire matrix once. That would be something like N^2. Even if you don't know like exactly how to arrive at this solution, you should be thinking along these lines because we probably aren't going to be able to do any better than that. Like this is a theoretical best case anyway. So now in terms of actually doing it, it's going to be pretty similar to the idea we talked about a few problems ago where we were talking about this idea of a difference array. Let me show you how it's going to work in one dimension before I show you how it's going to work in two dimensions. So let's just think of some really simple examples. So imagine like we didn't even have the rest of this matrix. What the difference array in one dimension means is that like let's say we wanted to mark this subarray and we wanted to increment everything in here by one. The trick that we would do is at the beginning uh we would put a one and then at the end we would put a minus one. Notice how I put the end actually one position outside of that. And the reason we do this is because now every prefix sum is going to tell us the value that goes in each position. So like the prefix sum of this is just one. That tells us that a one is going to go here. The prefix sum of this is also one. So we would put a one here. And then the prefix sum of this entire thing is going to be zero. So then we would put the zero over here. And the reason for that, I think it becomes kind of obvious now, is because we put the negative one here because we know that everything beyond this point doesn't have that plus one applied to it. So we put the negative one there to counteract that. So one idea you might have, imagine like this is the matrix that we were given for the first query. The idea you might have is do this for the first row and then do this for the second row as well. Well, that's fine. and it's technically going to work, but computing it for a two-dimensional submatrix. Now, like we could do this and this and this, but now when we get to like this one, it's clearly becoming a bit more complicated because we can't like include that. So, if we were going from left to right and top to bottom, it's going to get kind of complicated. And even if we do it this way, it's not going to necessarily be more efficient than just doing the simulation approach that we were doing earlier anyway. So we kind of have to think of a better idea, a sort of a shortcut. So I'm going to create two matrices and I'm going to show you generally how this solution is going to work. A bit of the intuition. So this is going to be our difference array or you could consider it like the difference matrix. And I'm going to have an additional row and column in it. And I'll kind of explain that a bit later. But if you remember how difference arrays work, you'll pretty much understand why I'm doing this. So this is going to be the difference matrix and this is going to be the actual result. So imagine we have an arbitrary value like this one that we're trying to compute. What value is going to go here? Well, imagine that I'm filling this guy in left to right, top to bottom. So what that would mean is that these values, these adjacent values are actually already filled in. Okay, but how is that going to help us? Well, remember what we're trying to do when we're in this position. We're trying to accumulate all of the ones that we've seen. And when I say ones that we've seen, I mean from the difference array, right? If we could set it up like that, we would be able to solve the problem. But obviously we're trying to do it without having to scan over every single thing. I mean, we're already at this position, but we don't want to have to scan through everything else that came before it. Well, the good thing is we don't have to because remember we're computing the prefix sums from the difference array. And assuming we have those stored, I haven't told you how we're going to have them, but assuming we have those guys stored right there, how can we uh figure out the value that's going to go over here? Well, we can do a little bit of interesting math. It's not really super complicated, but the value over here should tell us the prefix sum of everything here from the difference array, right? That's what the value here should be. And the value uh here should tell us everything in this section from the prefix array. Okay. So, if we add that and that, obviously, that's not going to give us uh exactly what we want. We're kind of double counting a lot of this section over here. So what we can do is then also get the value over here which should tell us this section from the difference array and then we can just subtract that and by doing this math consider this is the top value and consider this is the left value we're doing top plus left and then subtracting from that the value over here which is top left. So, I know this is kind of confusing cuz I put a plus sign here and then this almost looks like a minus sign, but I hope you get the idea. It's a pretty simple math formula. Top plus left subtracted by the top left. Okay, so that should give us this big nice section here and here. That should give us the sum of everything in that section from the difference array. And now all we need is just this value, which we can just read that from the difference array. So, that's not really complicated. Okay. So if we could do this, we would be able to compute the value of this in constant time. But that's assuming we computed everything before that, which we could do that in constant time. Like we could get this guy in constant time because we would just take the value here. There's nothing really up or to the left or top left. Though we would have to make sure we don't go out of bounds. So we'll add some like if statements to our code for that. But we can easily compute the first value. And then we can compute this guy by again just doing this and that. And then same thing here. And then we can just kind of do that from top to bottom, left to right. Each of those will be computed in constant time. But it's all dependent on the difference array. So how do we set up the difference array? This is really the clever part. So imagine that this is the square that we're trying to represent. So we would get a one in this coordinate and a one in that coordinate. But that's not what we're trying to do, right? Because what we want is for the sum of this section to be equal to one. Like that's what our whole solution over here depends on. We're keeping track of those prefix sums. This entire section should be a one. And that's why we should end up with a one here in the result matrix. That's at least assuming that this was our only square or only submatrix. So clearly this isn't going to work, right? So we definitely can't have more than one one in this submatrix. So why not just leave the one over here? Okay, that's good. But now if I tried to compute this submatrix, well, assuming these are zeros, I'm going to get a one. And that's not the case. That's not what should be the case. We should end up with a zero here because we're not including or when I say we should end up with a zero here, I meant in the resulting matrix. But clearly that's not the case. If we compute this entire thing, we get one and zero and zero. That's one. So we're going to end up with a one over here. That's not what we want. So to mark that, we can put a negative one right on the outside. That's pretty similar to what we did in the one-dimensional case. But this is where it's going to get more clever. We also don't want like this submatrix to have a total sum of one. We don't want to end up with a one over here. So we can also put a negative one right out here. So now the math actually looks really really good because if I try to do this, I get a zero, which we should get. Anytime we're outside of this purple region, we should have a sum of zero. So, I get a zero over there. I also get a zero over here if I try to do this because we get the negative 1 and plus one. And I also get a zero when I try to do this. That's good. We do want zeros over here. And I get a zero over here too cuz I do 1 minus one. So far, we're pretty good. We have a zero on this row. We have zeros on this column. If you try to sum this, this, this, or this, you're going to get a one in all of these spots. That's good. But it breaks at the diagonal part when we go further cuz now I'm double counting the negative 1's. So if I try to sum up all of these, I'm going to get a negative one over here. But that logically makes no sense. We should get a zero here. And the result uh it being negative -1 is because we double counted these two negative 1's. So to mitigate against that we just put a plus one over here. And this will work for everything not just here but it'll work for everything that comes here and everything that comes over there because everything that comes over here well uh from this section and to the right is going to include both of those for sure. And then the one is going to cancel one of them out. and everything over here and uh beyond it is also going to include this and this. So that's why it works and that's why it's kind of a clever thing to do. So basically that was a long way of saying that every time we have a submatrix that's introduced for the top left position we're going to put a positive one for the bottom right position and one position out of bounds we're going to put a negative 1 and then to the right we're going to put a negative 1 and to the bottom we're going to put a negative 1 as well or sorry here we're going to put a plus one sorry you can see how this is kind of easy to get your math confused and lastly why do I have this region out here well imagine that like the original matrix that we were given is maybe like a 2x two over here and that's actually one of the examples. Well, we don't want to go out of bounds and instead of just having like an if statement check, we can put a negative one in out of bound positions. Okay, so with all that said, let me actually go through this example. It's a pretty simple one, so I think that'll make things more concrete. So, uh the first matrix that we're given is 1 one. So, we put the plus one there and uh 22. So, at the last row + one, we're going to put a negative 1. last column + one, we're going to put a negative 1. And then at the diagonal, we're going to put a + one. And next for this one 0 0, we're going to put a one there. And we're going to put the negative 1 here, negative 1 here, and positive 1 there. So now I'm going to start computing this. And remember, why did we set it up this way? Because now if you compute any single prefix sum, you're going to get the correct value that goes there. Like if I compute this prefix sum, it tells me one's going to go here. If I compute this, tells me one's going to go there. If I compute this, tells me zero is going to go there. If I do this over here, tells me one. This tells me two. This tells me 1 + 1 - 1 is 1. And finally, we're going to do this. It's going to tell me zero. This is going to tell me 2 - 1 is 1. And this is going to tell me 3 - 2 is 1. So obviously that is the result. So it does work. It is correct. But I still the way I draw it right now I kind of just did the brute force, right? I just recomputed everything. So let me show you how it's going to work the other way. The way we're actually going to code this up. When we code it up, we're going to get to this position. We're going to take this value and add it with these three adjacent positions. But we're going to get those adjacent positions from the matrix that we're actually filling in, which initially is going to be all zeros. So that's out of bounds. So it's not going to do anything. So now for the first case we get a one. Okay. Now we're trying to compute this. How are we going to do it? We're going to take the value from here. It's zero. We're going to add to that above diagonal and left. Well, we're not adding all of those. Actually, we're adding this. We're adding that. And then we're subtracting that one. Obviously, these two don't exist. So, we just get a one here. And then over here, we're going to add one. Add nothing. Subtract nothing with this negative 1. That's going to cancel out and bring us zero. Over here, up is one. diagonal and left is nothing. Here is nothing. It's zero. So, we're going to get a one here. Here we get a one above this and subtract that. So, that's 2 - 1 + 1. That's going to give us a two. And then you can probably fill in the rest of this, but I'll go pretty quickly just to do this. 2 - 1 with 0 1. This is one. Nothing here. Negative 1. That's going to give us zero. This will be 2 - one with nothing. That's one. And then finally, this is going to be 2 - 2 + 1. That's one. And remember what that means. That means this one told us that that's the sum of everything of that in this. This one tells us that that's this sum. This two tells us that that's this sum. And that's why we're getting rid of it. We don't want to double count it. And this just tells us the original value. So that's why we add it. Okay. So the overall time complexity of that was, I believe, q + n^2. Let's code it up now. Okay, so the first thing I'm going to do is just initialize that difference matrix. I'm going to make it uh of n +1 dimensions. So in Python, that's pretty easy to do with list comprehension. So just like this. And then we're going to iterate over each query. We're going to unpack each query at the same time that we iterate. And then we are going to at the top left add one. So let's do difference matrix row one column one add one and I'm going to copy and paste this a few times because now in that same row all the way to the right so column two and then one position out of bounds we want to subtract one that's like our marker and then in that same column at row 2 + one we also want to put a negative 1 marker and then all the way out of bounds r2 + one and column 2 + one we want to put the plus one. So this is just initializing it. It's pretty easy once you know the math. And then I'm also going to initialize the result. It's going to be just n byn though cuz we don't want to have extra elements. And then this is also going to be duplicated n times. And then we can start iterating over this matrix and just kind of using the prefix sums. So I'm going to do this and I'm going to do this. And so what we want to do in this result row column position, we want to take the value in the difference matrix at that same position. And then to that we want to add the top prefix sum and the left prefix sum. But that double counts a lot of elements. So from that we want to subtract the top left prefix sum. That's assuming all of them exist. none of them might exist or maybe only some of them might exist. So to handle that we're going to initialize some variables. I'll say top is going to be equal to zero if row is equal to zero because we can't really go above that. Otherwise we'll do result of row minus one column. That's why we do the check because we don't want to set this to negative one because in Python that won't even give you an out of bounds error. That'll actually just mess up your code. So be careful about that. And next we want left is going to be zero if column is equal to zero. Otherwise do this. And then top left is going to be a bit more interesting actually it's going to be zero if either row or column is zero. So if this is zero or column is zero otherwise we will do result or yeah result of row minus one and column minus one. So after all of that we can just return the result. So, unless we have some messed up math going on, I do believe this should work. And yeah, you can see it does. And it's pretty efficient. So, I hope you learned something new today. Thanks for watching, and check out Necode.io for a lot more. or I'll see you guys soon.