Daily Leetcode #2220: Apr 29, 2026 - 3225. Maximum Score From Grid Operations

Added: 2026-05-06

[00:00:06]This is my bus.

[00:00:14]>> It is a very tactile bus.

[00:00:17]As you can see, [music] [music] [music] >> [music] [music] [music] [music] >> Hey hey hey everybody. This is Lavy.

[00:01:01]This is day 29 of the legal day challenge. Hit the like button and subscribe button. Join me on Discord.

[00:01:06]Let me know what you think about today's poem. Uh I am here in Sri Lanka uh in this beach town of uh Hikadua.

[00:01:18]Uh hope you like the intro the videos and stuff like this. I'm very tired. I didn't sleep well or my flight was at like 1:00 a.m. So I just didn't sleep that much. Slept on the flight. Woke up and then kept on going and then passed out during the train ride as well. But uh here I am uh trying to do this pro turn some lights.

[00:01:40]Looks a little bit uh you know I hope everyone's doing okay. Uh I I don't I I don't remember this problem. Uh and I haven't read it yet. That's why I don't remember it. But I my disclaimer is that some people pinged me and said this was ridiculously hard. So we'll see how it goes. I don't know anything about this other than that it apparently is very hard. But uh yeah today we have 3225 maximum score from grid operations. All right you're given a 2D matrix grid of size n byn initial all cells I kind of regularly remember this one but let's see or in the sense that like I remember it was hard. Uh okay. So we have n byn grid. All cells of the grid are colored white. Uh in one operation you can select all cells or any cells of i j and color black all the cells of the j column sum starting from the top row down to the i row. The grid score is a sum of all grids of i and has a horizontally adjacent black cell. Return the maximum score that can be achieved after some number of operations.

[00:02:48]Okay. Don't uh Okay. So, we have to we can color some black cells and then you score everything next to it. Right. Is that the idea horizontally? So, yeah.

[00:03:00]So, here you look at Right.

[00:03:08]Um N is small. So we can maybe take advantage of that or we probably should.

[00:03:16]Uh this number is big. So we have to do it. Um okay.

[00:03:24]So also it's n by n. So that means that um there's nothing like asymmetric or is symmetric right?

[00:03:32]So um that could mean something. I don't know. Uh what I mean is that because it's 100 there's no um like 2 by 100 type things. Um, right.

[00:03:46]I think if I remember, uh, I don't know.

[00:03:49]This one's hard enough that I kind of remember it. I just remember I would I don't know if scared of it is the right word, but just fearing it a lot. Um cuz I think the idea is that you have to like keep track of states a little bit, right?

[00:04:16]Um, I we I guess I did not learn anything last time because I don't remember anything. I'm I'm you know trying to see if I could use my memory to remember. I remember doing this during the contest though and it was hard. Um, okay. So the first thing that I would try to think about is just try to think uh come up with some ideas or principles that you can kind of build on, right? I don't know that I have anything like that. Um some ideas is that okay well um well I mean there's two ideas, right? One is that you can select the black ones or you could select the white ones, right?

[00:05:03]The white ones. Um I don't know which one's easier, right? Because if what does a black cell mean, right? Um a black cell means that you know it is n is equal to 100. So we can figure out you know uh it has to be n cubish right. Um so I I think I mean it feels like a dynamic program form but a dynamic program for means that we have to figure out how to figure out the states right so you know maybe some really naive version would be you know we have to the column and then and then uh try to figure that out right what does that mean though Um because then now what it means is that you have to keep track of the previous columns uh at least height, right? So maybe we could do like P height. I don't know if this is true.

[00:06:08]I'm just uh I'm still trying to work it out, right? Because that that means that you know you kind of draw it out.

[00:06:22]Uh oh. Do I have it on screen? No, hang on.

[00:06:30]Now it's all over my face.

[00:06:33]Um, yeah. So then the idea here is that I don't know if there's anything to take advantage of the fact that it's n byn.

[00:06:44]Um, but I don't know. Let's say we have this. We call this black, right? What does that mean? That means that we can now take uh the sum of this thing, right? And how do I change the color? And that part is not so bad because you could do it with like a preix sum or whatever, right? And then now what? And right then now you could have two things, right? Or three, I suppose. They could just be even. You have something smaller, which doesn't mean anything.

[00:07:17]You could have um except for now because you have the previous index maybe you can do uh then now uh these things are added right and then you have another case which where the yo and then the other other case is that uh and you can maybe use another one in anyway no the other other case is something like oops that's too big uh you know if it's bigger then now you you do this case, right?

[00:07:54]But then the thing that you have to think about uh or be careful anyway is that um you know you have something like this.

[00:08:05]You do not double count the things here, right?

[00:08:16]So that's kind of the thing.

[00:08:21]I I mean this seems pretty okay so far, but maybe maybe the complexity is why this doesn't work. Um because it feels like this doesn't have them. I don't know.

[00:08:34]I'm also like being very cautious because I feel like I don't know. Um because then you also have like different cases actually I'm just trying to think through the different uh cases in my head right cuz the thing is that okay we have you know what what happens if you have something like this right like we this and then we have this. So then now we want to count this, right?

[00:09:14]But then now what if next one we have someone like this? Well, here we only want to count this and not this, right? So you have to be careful how you store these things. And the previous height is not nec because one way that you could, you know, uh the reason why I said like that is because one way that you could think about handling this edge case is just pretend this height goes up to here, right? But um but as a result now if you do something like this then you have you can only go up to here and you can't store both because if you have a loop inside that's already going to be n to the fourth right?

[00:10:11]just looking at the form.

[00:10:18]Also, I I just want to say maybe this is a little bit too late to say this is a bull crap problem. This is this should not be on an interview that you do, but uh I don't know what is this uh Uh, I mean the end to the fourth one would make sense. We have an if we just able to do one more state. Can I generalize that a little bit better?

[00:11:02]Right?

[00:11:05]>> Maybe I'll just write out the end to the fourth. Um, and maybe it shows up.

[00:11:12]Because sometimes you could when at least for me visual having code written is visualization and having that visualized allows me to be like oh right I could just you know uh uh compress it a little bit but uh I don't know.

[00:11:31][sighs] [yawns and gasps] I'm not a super uh let's bring back the visualization because I'm trying to think I mean another way that you can think about doing it which I don't know if I hand is just figuring a way to that they uh cancel out almost right um like having attributing like negative score or something like this so that um yeah I don't know I'm yawning a lot because if you my body apparently feels like it needs energy to um use it That's a tough case for what bring do end to the fourth. I don't know why because the the case is uh just you know either this or the alternate of this right and of course you have this case but oops but uh but you could also have for example this case right then now you have to add in well here right which maybe is not that bad to do but like I said you have to be able to handle um these three cases of and as a result how do you do it without recording uh well I mean this index being a state I mean can really uh um can't really get rid of it but then these two states right how do you get rid of it or one of them rather I mean another way is I mean and That's the same as just putting like the previous one, but that doesn't help us enough, right? Is there I'm I'm trying to think if there's a way to represent um to represent this in terms of Huh?

[00:14:44]Well, this only happens if this is smaller, right? Because if you have someone like this and then it goes this, then this has only one state.

[00:14:57]Uh like it doesn't have this weird uh double thing, right? Okay.

[00:15:03]So then what does that mean?

[00:15:08]That means that if it's smaller, I mean I still don't know how to reduce that though, right? It just means that Okay, fine. If it's bigger, then it's simpler in terms of if statements.

[00:15:22]But how do you get rid of a state?

[00:15:27]If it's for if it's smaller. Okay, so okay, fine. Maybe we have a thing. Do this. How do you get rid of this state?

[00:15:35]Right. Um, so which one do you store? Do you store this one?

[00:15:42]Can you store this one with like a negative weight so that we just double counted but subtracted like twice or something weird, right?

[00:15:59]like not subtracted twice but I'm trying to say like um yeah you do the math in a way such that um do the math in a way such that it just cancels out um okay let's think of another case though right or not another case I already kind of drew it of oops someone like this this what does that mean thing is that if we do this right Then we have to so that okay so we want to only calculate this. Can I do math on this?

[00:17:08]Right. Like can I um can I here add this and then subtract this or something like that. All right.

[00:17:38]Well, I guess we can always subtract this.

[00:17:49]Wait, what? What am I doing? Uh um what does that mean for iteration? Cuz for this one, all that matters is that we have this and then we just keep we subtract this.

[00:18:22]And if we go past this Then we add it back in anyway. Can we though?

[00:18:32]Do we add it back in?

[00:18:35]Okay. What is the idea here? I'm think I'm not being clear because I'm not going to myself, right? So, okay. So, let's say we are doing this one and then we just assume that we will add in all this, right? And then, of course, we have to subtract this back out, right? So then we just add in all this stuff and then okay. So then now on the next thing we add this which is just subtract this. So nothing changed. Nothing changed. Nothing changed. Nothing changed.

[00:19:08]Nothing changed. But then uh what does this mean?

[00:19:19]Because we always subtract that out.

[00:19:24]So we add all that, we subtract this. So then we have to kind of figure out a way to add this back in, right? Or am I doing this weird? No, no, no.

[00:19:36]Also, I am doing it weird cuz all I am doing um I don't need to boost stuff, do I?

[00:19:45]All I need to do maybe is just add this part which we can do for prefix. some oops this part and then just incrementally subtracting it.

[00:19:58]That even make sense.

[00:20:03]So basic uh does that count all the cases because then now if we go here that's fine. We already assumed that we uh did this. We go here.

[00:20:35]Do we subtract?

[00:20:38]I guess we do subtract this.

[00:20:41]No, no, no. We don't want to subtract it. So, I guess we have to add in all of this stuff then, right?

[00:20:50]And then we just kind of um as we go.

[00:20:53]No, because then if this is smaller, you don't want to add this. And how do you prevent this thing from double counting or whatever?

[00:21:11]What is the maths?

[00:21:22]Because here on the top part you subtract because you want to subtract the stuff that you added by default.

[00:21:31]Here you don't want to subtract because we didn't add, right?

[00:21:51]>> [sighs] >> Okay. So um this case is easy because you have given this and you just do this and do the math that way. Maybe uh this case can we do it is just this thing minus this thing maybe.

[00:22:48]Yeah. What am I thinking of?

[00:22:52]Oh, no. Well, yeah, you minus here. But if we have the other case of here, you don't minus all of this, right? You only minus up to here. You only minus up to here.

[00:23:22]I don't I don't want to spend an hour on this.

[00:23:30]Who writes these kind of problems?

[00:23:38]Oh, why is these kind of problems?

[00:24:07]Maybe I have to think of it in reverse.

[00:24:08]All right. How do I think about it in reverse?

[00:24:14]Okay. So we stick a thing and the next one is bigger maybe then now what then we just kind of uh okay well I mean that's easy right we just do this part and then if we keep incrementing we just keep on doing I guess that's not not much to do on this one uh so then now the question is really just one of these things right oh I guess This this first and then one of these things.

[00:24:56]Okay, let's go for the cases again.

[00:24:58]Maybe I'm just being confused. Um, okay.

[00:25:01]So, let's say we have this one. What does that mean? Right, that means that if we do geometry, we do this and then we minus this.

[00:25:13]Okay.

[00:25:15]So that's this minus this, right?

[00:25:21]Okay. So let's say this part, the second part. What does that mean? That means that we take this.

[00:25:31]No, no, no.

[00:25:34]Wait. Oh yeah. That means that we take this.

[00:25:41]We minus this. But we got negative right without keeping state and you should not get negative.

[00:25:57]Okay.

[00:26:01]The alternative is if if we have uh the alternative is we just take this and then subtract this. Right? And then now for this one then we might have this but we only subtract this do we well we definitely subtract this.

[00:26:30]So we're going to go up to here right in the subtract.

[00:26:37]Oh no no no. In this case, actually it just goes up to here, right?

[00:26:42]Because Yeah. Okay. And then now what if it's longer, right? This one then you have you subtract up to well, it only goes up to here. So I guess you would do some maths about subtracting all this.

[00:27:09]which is fine. And then we add stuff to the left because it's bigger. Did I solve it? Is that right? Am I just confusing myself?

[00:27:20]Right? Cuz the last one would be okay. You you added this extra but you know that what the index is. So you do this just subtract this part.

[00:27:36]Um, I mean it just go to zero anyway because this part you don't subtract but but you wouldn't really do the sum of it, right? Uh, but then you add the previous one. Is that it or am I just like did I miss the cases?

[00:27:59]I think No, cuz here I see the thing that I'm still not getting is that. Okay, so we we took account this thing, but here in this one in this one, we have to add back in here and we don't really have a way of doing that yet, right?

[00:28:32]Yeah, that's why. Okay. So, we have to add back here and we have to by that we have to know this. Oops. We have to know like this length.

[00:28:51]How Yeah. Okay. I think that's why I I couldn't figure it out. I mean, it's >> [sighs] [gasps] >> And also what do you pass forward? I guess you pass for this height, but then you also want to almost pass forward all the way here, right?

[00:29:52]So I don't know. Oh my god.

[00:29:56]At some point, I think I'm going to give up on lead code. It just makes no sense that they do stuff like this. It uh doesn't really like I don't know.

[00:30:28]try to solve it with geometry, but I don't think I'm doing it.

[00:30:45]Also, this doesn't even make sense. I think I'm just confusing myself because we add all this and then we subtract all this. But it's not just that, right?

[00:30:56]Because we also this doesn't get filled in anymore, right? So you have to subtract this part.

[00:31:03]Actually, does that make sense then? Cuz if we just did all this, then we have to subtract this part, right?

[00:31:11]No, no, no. You want to subtract this part and you subtract this part. Well, technically here you subtract all of it, but >> [snorts] >> So then what does that mean?

[00:31:34]So you want to subtract at least this but up to that maybe. So you want to sub you always want to subtract this and this and then here what does that mean?

[00:32:00]That means that if we also I don't know if we always subtract and just don't add it. Right? What what am I what am I confusing about? Um because we have prefix sum we can always add whatever we want.

[00:32:15]So here we we we want to add this and then subtract this.

[00:32:29]But we don't know what this amount is.

[00:32:34]All right.

[00:32:43]because because you want to well you okay so maybe I'm just confusing myself with what a drawing is hang on okay so for okay so we want to add this uh let's just say we want we add this part right what does that uh from which is this part is what I'm trying to say except even up. So we add this part we get to the thing and we subtract this. Right? That would work.

[00:33:24]Okay fine. Right.

[00:33:28]But what if we add this and then we don't subtract if we have a bigger thing. We don't subtract all this. Right?

[00:33:37]We just subtract up to here.

[00:33:42]Oh yeah, we add.

[00:33:50]So that's the part that I don't know how to do it, right? Because we have to stop.

[00:33:58]Yeah. So to get this geometry, you would get this, right?

[00:34:07]to get this geometry.

[00:34:10]It really just is uh like how do you know this without you know recalculating it right or without like how do you know this line without well storing it as a state?

[00:34:27]I think that's the part that I'm having trouble with. Um and then you have the big one. So this one requires us to know this one, right? Um because then now we have to draw this one. So I don't know.

[00:34:40]I mean we have to get rid of one of these states. And that's the problem that I'm trying to figure out, right?

[00:34:47]Or reduce it to like I don't know something smaller or something, right?

[00:34:51]Like it could be a dimension but a dimension of like X or whatever, right?

[00:34:57]Um, I don't know.

[00:36:01]I'm just keep on looking at the forum statement hoping that it would change.

[00:36:05]It has not changed by the way. Um I feel like I've made no progress in half now either. I think that's also a tragedy.

[00:37:12]What? Okay, let me rethink this. Right now, we've been adding stuff to the left and to the right. What if uh what if we just add something up, right? Or I don't know. It is just a crazy idea because I have no idea, right? So, okay. So, what does that mean? if we've cuz I think right now I've been focusing on the horizontal aspect. Okay, let's say we go here, right? Uh what does that mean?

[00:37:36]Uh okay, I don't know. But then now, okay, let's say we So then now we have two things, right? Let's say we have lower then now we just push this right with the previous, right? Um if this is bigger, then we don't push. Okay, so maybe left and up. Can we focus on that?

[00:37:54]So, I mean, okay, so this is Gucci, right? Uh, okay. So, here, then we go up, right? Uh, if we go, but that's the thing that I guess we've been trying to do, Larry, because here, then now you're trying to figure what up is. It could be here, right? Um, okay. Right. But then now, uh, if we Why is this black? My I feel like this looks grayish. If we go here then it is left but then left is overlapped by that thing right which is but then here I guess that I have not changed anything right because now we still go for the left which is here right so then we that means that we need to know this and this for the up part right uh which is two two previous data along with this one which n cube Okay. Uh number of states which makes it end fourth of the loop. Okay. So we've been saying the same thing uh again and again.

[00:39:01]Is there anything we can reduce?

[00:39:15]Can we assume? Okay, maybe I can think about it this way, right? Instead of going state by state, which I think that's all I've been doing. Uh what if we just assume what if we create a constraint of [groaning] am I thinking this right? Let's say we have instead of doing the loop because right now I'm thinking of okay well I'm at this index. I'm doing the loop and then this loop will tell me some stuff about the left or or um what's I keep going up but just like what's whatever right I guess I'm visualizing upside down I don't know but what if we just enforce itself right so here we recurse into the smaller one so then we keep track of here and then here we can recurse into here or we can recurs into two things, right?

[00:40:15]Okay, I think like Okay, so here we know this thing. So then we can just store a boolean thing for checking um maybe this area and then we could also pass a boolean thing for checking uh this area and then we just have to do a loop from here to here. Maybe does that help or even right if it just has to be bigger than here then now we can do the math differently right okay so let's say we got rid of this case then what does that mean that means that now we effectively treat this as the thing right so then now we just do um all the way up.

[00:41:15]Well, we treat these things.

[00:41:21]What does that mean?

[00:41:26]Okay.

[00:41:36]Okay. So, let's say we uh I don't know.

[00:41:40]Let's say I I don't know. Go take a nap. Um cuz if this if we it's something like I feel like this could work though cuz here then now you only loop through the thing. You could pass this in as the thing and then here maybe you also pass in another thing where um you know well uh you only have this case.

[00:42:09]How would that even work? Okay, so basically or maybe uh maybe this is a little bit too much as well. Maybe the case is just okay. Okay. So you have this now you you loop from uh whatever this height is up and then you get this without thinking about it. Right? Okay. So then now what if we reduce it the other way of okay now we're thinking of the smaller cases.

[00:42:39]Right? Then now we only have to worry about um worry about the the this thing uh these two cases. Right? Then now can you though can you worry about only these two cases without capping it here?

[00:43:02]Oh, I see. Maybe then now it can go bigger for sure. You just don't count this part which is would be incorrect but that's okay because you save the state.

[00:43:15]Is that the logic? Maybe because then now Okay. So the idea here is that okay well we just use this as the thing um that then now what right that means that we only have to differentiate between these two and anything that goes higher would just be incorrect for that recursion but that's okay because we handling that case in another recursion a classic thing of DP doing more but but but correct because those other ones would never be optimal which I don't remember I feel like we did something similar not that long ago but that could be a thing okay then what does that mean then let's just say we don't care about this case right so then now we only have to worry about this height and what I think we already solved this part but I I'm there's a lot of stuff going on okay so we have this height so we want to add I see so then now we want to add just this part how does that go maybe this Uh which one do we want to draw? Okay.

[00:44:49]So we subtract this from it.

[00:44:54]So we want to add just this part then right. So okay. So the next step we add this and then we subtract this.

[00:45:04]Right.

[00:45:07]Um, no. Wait, what?

[00:45:16]Hang on. Hang on. What are we adding when we subtract? I feel like we're close. Uh, but uh I'm not getting it quite right.

[00:45:25]So, the thing is that Okay, so we do want to No, we don't. Oh, well, no.

[00:45:30]Okay, let me let me reframe this. Right.

[00:45:32]So, then now this is the maximum height.

[00:45:34]So, then we do because I think I'm still confusing. I'm still trying to solve for the right side which we shouldn't. We should solve for the what I call upside even though it's technically the downside. So then now here we solve for this given this height and then we're Gucci. And then if we go and this part we don't solve the left because we already solved it using this parts uh downside. Um so we don't care about the left which is going to be incorrect for I mean which is correct actually all the way up to here because our assumption is that because of this line all this will be calculated but and then everything if it goes past that this is actually wrong but that's okay because we're recursing it in a way such that we recurse with this and we're going up All right.

[00:46:29][sighs and gasps] Did I get it?

[00:46:37]Maybe. I don't know. To be honest, I'm not quite sure. Let's uh let's uh I mean this is the thing where like I you can't see me do it, but I'm like all tapping between this and the things as I implement. If I have two screen, I would just have two screen and not all tap.

[00:46:53]But um to kind of figure out, right? So index uh 0 to n right whatever uh n minus one whatever right p height uh the height that is relevant this is actually not p height anymore but um because the height that is relevant depends on this thing right go up u meaning h maybe go up is not quite the better word but uh whatever um okay so let's Let's actually define it precisely though, right? If this is true, um that means that we want to calculate the score of the left side of the bar of the current bar.

[00:47:45]Maybe uh if force we want to calculate the score of the upside of the current bar and which is I guess downside I don't know but uh okay right I hope this makes sense to people at home because well honestly it's hard for me to say in a way to make sense to you because it barely makes sense to me right but these are two scenarios. Uh I'm going to try make an attempt to explain it. Obviously um if I solved it then it would have been much faster. Let me rewrite this from scratch. Maybe a bad move and that I should not have deleted it but whatever. Right. So okay.

[00:48:28]So now we have this case right.

[00:48:33]Um so then we just recurs it into two scenarios of um of okay. Okay. So the next bar um so the next bar we can either calculate uh what I call calculate upwards which means that we calculate this this score which which um you only and this [clears throat] only makes sense in the context of um on the left side of it it is filled right. So, so the the context here is that well, let's just say we're looking at the one next to it, this one.

[00:49:17]What I call count up is that we count this part, right? Because this part is covered by um cover covered by this part, right? And we have the height to kind of like you know because the idea here is that um and this is just in general is that we have this then now um uh you could say that this bar covers here.

[00:49:42]And so anything that um and we don't add it yet but anything that you add a bar to then now you want to fill this in and calculate the score up to whatever this height is. Right? So that's one scenario. um ext.

[00:49:57]Yeah. Right.

[00:49:59]And then the other scenario uh and I'll draw like a little weird thing here as a as a sub thing, right? Is that um we calculate to the left, right? So, you know, it's just yeah, let's just say this uh you know, you have something like this. Then you know that this is higher. So, you want to calculate to the left of whatever this index is, right?

[00:50:24]And that's it. And then you just get this chunk. Um, and that's it. And the argument here is that the combination of these two with uh will generate or will allow you to um take advantage of it in a way such that you're not um that'll give you the optimal answer. Um, it actually technically is like goes into not it doesn't go to well, it doesn't go into incorrect states, but the incorrect states are incorrect in a way that they'll never be optimal because they'll just give you a worse answer, right? And because you you're giving a worse answer um like it's okay to calculate them, it just won't give you the best answer because the actual answer um exhaustively will actually show up, right? So that's kind of the idea and then the idea behind okay now we have these two ideas then the the thing is that this actually takes account this test case of okay well uh you know let's say we we well at this index you know we loop through this one right so we know what that height is and we know the previous one so we know what this height is so then now what my argument is that okay so we have extend this line, right? Uh you only have two things, right? So here, um so if it's smaller than So if it's I don't Man, I forgot which way I did it, but yeah, let's say let's go the easier one, right? So if it's here, it's bigger than the green line.

[00:52:01]So then we just do the um add left or whatever you want to call it portion of it, right? Because then we just add this part to the add left, right? Um if it's smaller then we just go um up right we go up to this line right um yeah we go up to this line right so then it goes up to here right um and then the only other case is if you have someone like this right um and and the thing is that well in fe wait does that do even.

[00:52:40]Oh yeah, yeah, yeah, yeah. So then the idea here is that here we we go up, right? And then we loop. Um, in theory, the idea here is that you when you pass the recursion forward, you don't know the green line anymore, right? You don't know this green line rather. You're you're passing it here for uh this line for the go up thing, right? So then here for example it's easy to do a go up because it only goes up to this line as we know. Um but here the problem is that you here if you have something like this you want to do a go up up to this line which you know um well we don't have right. So as a result what happens is actually um what happens is actually that well you just have this. So you don't go left because you don't do calculate left, right? So you don't calculate left to here. And as a result, this is just going to be a suboptimal answer. But that's okay because you're going to catch all the way through. So anything here, well here it's correct because you don't want to add this anyway. So actually that's just correct. So right because this is already this stuff has been calculated by this one's go up in theory, right? But then the idea is that if we go here, well, we don't calculate this because we're trying to calculate what's up here except for this line is actually back here. Um, but that's okay because because we have a go left that starts here um recursively and and that will take care of that case. Um, that's kind of the idea. And I honestly some part of it is me convincing myself more than I'm convincing you. Um, and some of this, okay, I think I have the idea down, right? But the transition is still uh going to be a little bit tricky. Um, to kind of make sure that I have correct, right? So, so let's go through it a little bit. Um, and technically you probably have two functions here. So, maybe we'll try that, right? um in sub true force uh let's let's do it that way then right uh let's let's have two functions right uh I don't know if that's a little bit cleaner or not right so this is uh let's just say f left and f up right maybe f left and f up is correct but uh uh calculate the scores from the previous height on the left side or something and then you have another one which right the height that is relevant and the context is relevant right uh that's why I don't think these comments are very good the previous height on the up side it's actually I don't know I like up uh now with f up right so I don't know uh okay so what is the base case right um Okay, this is where I need to kind of bring this back and forth kind of in my head, right? So, I'm just all tabbing.

[00:55:48]Uh, just save the image if you think it helps, but it's for me. I'm going back and forth so I could kind of work work through this, right? Um, okay. So, now we calculate on the [sighs] upside, right? So then now cuz okay so we calculate the upside what's that mean that means that we don't care about the left but then this is going to be um if you calculate the upside what does that mean that means that the on the next one. I'm trying to work out the translations on the next one.

[00:56:39]Um, this is hard. Okay, so we we just calculate the up thingy. That means there's nothing to the or there is something to the left. But this thing is going to be the new barrier for the future's left side, right? So that means that um do you know what that means? Larry, is it easy to do the other one first?

[00:57:16]Okay, maybe it's easy to do the other one first. I I'm trying to not go jump back and forth. Okay, so then let's calculate the score on the left side, right? Um Oh, I guess we have to do prefix sum first. But we can uh prefix sum is easy, right? or at least I should know it. So it's fine. Um I'm trying to work out the hard part real quick. Uh okay hard parts. Okay. Cated the height on the left side. So that Okay. So then now the previous height everything that is past the previous height. Um yeah everything that's past the previous height we want to add score to. Right.

[00:57:58]Okay. So maybe we do something like um okay let's do get an end first.

[00:58:06]Uh so okay uh if index is equal to n then just return zero I guess we're done right. Um okay so index is zero. What does that mean? Uh if index is and maybe we just write write that index is zero. Well I mean this is a loop right? Okay, index is zero. We just set up the height.

[00:58:31]I don't know, maybe we just deal with that a little bit later. Okay, index is one and the previous height is zero.

[00:58:36]Just for the Would you ever I guess you would I was going to ask a question.

[00:58:41]Would you ever color the first row or first column? Uh you would if all your values are in the second row or second column or whatever, right? So, okay, fine. Um okay so then let's say the previous height is zero. What does that mean? So let's just write out this loop because I think that's my idea anyway. Um then now if I is greater than height then um I don't know score is equal to um let's say p sum from of the index minus one from height to i right something like this I mean we can fix this later that's so okay so that's the score, right? Because we're we're calculating we're calculating to the left. And then now because we're calculating to the left, the assumption is that this number is bigger.

[00:59:43]And because this number is bigger, um oh, and then I guess in that case, we can actually just start from height.

[00:59:50]Maybe even height plus one. Maybe just height would start height, right? Uh so that you could see what Okay, you only cut. Yeah, because the smaller one doesn't make sense because you just have zeros the entire time. I don't know. It's it's an unnecessary optimization honestly because it's just distracting. Okay, so then now you calculate to left and then now what? Right. Okay. So this is what my diagram I will refer to later or now.

[01:00:18]Okay.

[01:00:19]Uh if it's bigger then I guess what's the recursion?

[01:00:25]So you the next one either you want to calculate to the left or up right. So um so the up part it's going to start with height. So you want f left of index + one uh i right for the new height or if it's smaller then now it's going to be f up uh index plus one probably and then oh i is i is the height. Okay. Uh, that's why I keep on saying height and go up because I I could I mean I guess technically you could say it going down in depth it but I think that's why I got my up. I I was curious where I got it from. Okay. Um, so then up will only go up to I guess I right.

[01:01:23]Yeah. Cuz everything on top Yeah. Yeah.

[01:01:26]Okay. Yeah. Yeah. Yeah. Yeah. So then it's just this, right?

[01:01:35]I don't know if it should be zero or negative infinity, but I think it's fine.

[01:01:40]Uh something like this, right? Okay. And then now what's up? Up up it's a little bit tricky maybe.

[01:01:54]Okay. because then now you have height of the previous one that we care about.

[01:01:59]All right. So then now uh all right let's just do the dumb base case first.

[01:02:05]Um, okay.

[01:02:15]So then it goes only goes up to height.

[01:02:18]Maybe I I know that I wrote infinity more on the other thing, but um and maybe it has to be inclusive. I'm not quite sure. Um, so then the score is equal to the thing that goes up to the height.

[01:02:39]Uh, f up recursion is a little bit off, I think.

[01:02:45]Maybe. Well, no, it's just No, no, no. I just haven't done it yet cuz F left is probably makes sense, but F up is the one that um Okay. So, okay. Okay. So you have the height of the previous one if it is smaller than that height. Okay. So actually yeah if it's smaller than that height but we want to be able to go to infin. I see. Yes.

[01:03:12]Maybe.

[01:03:16]No. No. No. This is right. You just have to be able to go recursion on it. Maybe.

[01:03:22]I don't know. This is weird. Okay. Fine.

[01:03:24]Right.

[01:03:28]Uh yeah. No, no, no, no. This is this one.

[01:03:33]So you look at the P sum from I to height. I to height inclusive, right? Um okay. So that's the score for this one that because that's the height that you care about.

[01:03:52]What is the other height? I and after that it well it goes into zero but we have to be I see because F left only goes up to from height.

[01:04:24]Does it though? H I mean everything is zero but there is value in the recursion. No, cuz this would just be wrong.

[01:04:37]Yeah. No, cuz in this case actually it would be wrong in the other way of um cuz I'm bring back in a second. You could actually do this but um but it would just be wrong in that if you uh was that P left. So it's like calculating.

[01:04:56]No, you can't. Okay. No, no, no. It would just be wrong because we would double count. No, no, I was wrong on it being wrong. I think this is right. Um okay. So it has to saw here. But then now Okay. So then now you have the height, right?

[01:05:15]So okay so then it goes to how do you recurse the um so okay so this is smaller than the previous height so we already established that is shorter so then now we recurs that into okay into P up or whatever f up of index + one and it only goes up to i, right?

[01:05:52]Yeah, because it only goes up to i and then that's it. What does the thing do?

[01:06:15]No, no, no, no. It's I Wait a second. What am I doing? Okay, so this is P.

[01:06:29]I don't even know if this is quite right. Uh, this is P left maybe or F. I thought I think P uh F.

[01:06:39]Okay.

[01:06:42]Okay, what I slow down. What is this scenario doing? Okay, so you're doing you you're getting this chunk, right? So that's the score. And then now what's the recursion? And the recursion is that. Okay. Well, you have here you want to do left on height so you don't double count.

[01:07:11]Okay. So, F + one. So, height plus F up of X + one.

[01:07:23]I right something like this I don't know if this is quite right but it's something like this maybe uh it's very hard okay then but then we still haven't considered this zero case yet um maybe that's fine actually uh oh maybe it's fine in that we've already done it uh actually does this work we just keep going up, right? Uh, do we go all the way to iron?

[01:08:04]What happens? So, this is up, right?

[01:08:06]What happens if you go the way there?

[01:08:07]It's going to be suboptimal, but that's fine because we want to set it up for the next one, right? Um, in in case that the F left cannot.

[01:08:17]Uh so that's going to be so there's no additional score but it is just is an F left cuz this is now higher right oh yeah I mean there is an F left you just go uh index plus one and this is definitely just the current height no it's going to be I because I is the new height plus F up plus one.

[01:08:59]This will also be I I think I don't know if this is right. I feel like it's on it's it's on a boat. I don't know if it's the right boat, but uh yeah, I don't know. And then the first one is just going to be I don't know what the base case is. Uh zero, right? And then the previous is just zero maybe. Uh and then maybe max of this f up zero maybe. Uh and then piece sum.

[01:09:34]I'm lazy for now. I just want to see correctness. I'm not worried about performance. So uh yeah. Uh, so what I mean is that um I'm just going to do a for loop for now.

[01:09:51]Easy optimization, but I I don't want to think about it.

[01:10:06]Let's let's give it a spin. Uh, okay.

[01:10:09]Well, 32 thou 100 is probably not right.

[01:10:13]Um h I don't really have any subtractions under the negative infinity.

[01:10:22]Why is that? Uh why would that even give me that?

[01:10:29]There's no negative, right? No.

[01:10:34]How? What? How do I even get that?

[01:10:37]I don't know why men though, so maybe there's some like weird thing there. Uh why do I why did I write men? All these things. I think I'm just dumb.

[01:10:50]Okay. I mean, this is obviously wrong, but that's fine. Uh at least it's more reasonable than the other. How do you even get 64, dude?

[01:10:58]Um and performance is probably a little bit slow anyway. Um h you could say I effed up. Okay, fine.

[01:11:18]Huh? That's interesting actually. Uh how do you even get 64? Does you even get You don't get 64 if you add all the numbers together. I don't get it. I don't get it. Okay.

[01:11:31]Uh well, maybe the bus Should it be plus?

[01:11:39]I just write I honestly I just wrote plus out of instinct. Uh maybe that's not a plus. Maybe that's part of the max.

[01:11:49]That one doesn't make sense. Uh also I messed up anyway because this should be this and then this as well. Uh because uh I just didn't put in the score for some reason. Right. Okay.

[01:12:08]All right. All right. The numbers look a little closer. Still not good per se, but is it even possible still? Five, five, 14 sum. So 14 sum 19 is probably not right. Um all right. All right. But at least now with the differentiation between these two silly boys, okay, they're both wrong, but uh f up 0 should make sense. Okay, we could just trace it real quick. 0, right? Um, and by that I mean I will print it out.

[01:13:02]Does that help at all? Probably not.

[01:13:05]Uh, yeah. Okay, maybe not. Uh, well, let's see.

[01:13:18]I mean, we're obviously double counting somewhere, right? So, I guess that's the biggest thing.

[01:13:28]So, you calculate the score up up to the height, right? This part is probably right. Seems pretty straightforward.

[01:13:45]I actually thought that we would underount to be honest. Um because I'm not I mean the the first overounting makes because we added them but I thought that it would be um underounting. I'm a little bit surprised. Um that's why I don't really have an immediate idea but uh Okay, let's do F first. Okay, previous.

[01:14:20]Oh, did I mess up? Uh, okay. Yeah, maybe if index is equal to one, return zero.

[01:14:28]Maybe something like that.

[01:14:30]Okay, so that made it a little bit improvement. That's where you got the two from in one of them. Um, still not right, but uh, you know, that is definitely a bug that we had to fix. Anyway, um, I I was and I knew that one because I was thinking about it when I was writing it, but I just forgot. Uh, okay.

[01:14:51]Okay. So let's say we do the left the the double I is kind of uh it's kind of awkward but uh the left constraint is the left F left right F left goes only up to I right so is this right F left I so everything pass pi.

[01:15:24]Yeah, you're going to left because only when you're monotonically increasing or you're just increasing in general, right? So, okay. So, but up part, right?

[01:15:34]Up part. Does the eye make sense? Well, up only goes up to the height. So, it's not quite the same idea, right? Okay.

[01:15:45]Um, I think this is the I mean, okay, let's just think through it, right? Okay, so it goes past the height. So that means I guess this part looking like this part makes sense. Is there a score?

[01:16:04]Well, we're only calculating up and that means it pass height. So no score. Well, the score is zero. Okay, so this probably makes sense. This part, does that make sense? Okay. So, you go up to the height. This part I I don't know.

[01:16:18]But okay.

[01:16:20]So, then the height.

[01:16:23]Does this make sense?

[01:16:26]What did I confuse? No. No. I is the new height because we're going down. So, that makes sense. We calculate the left from the height up. That also makes sense. So, then Okay. So, everything makes sense so far.

[01:16:46]Did I confuse things? No. Okay. I was just also curious whether like I don't know why they flipped it backwards and up or whatever from the top down or whatever. Um, so I can double I think I'm doing it right on this one.

[01:17:02]And that's maybe why I counted up. But okay, fine. Um h this feels right if the logic is right but and I the thing with this is that I would expect it to underount if we were missing cases but because we're over counting with double counting that means that some of these cases are wrong which is harder to fix than missing case because we're missing case well you just have to find out what you're missing and then you could solve it but uh I don't know all right let's see does this help So we have the four 4 0. What does that mean? Four 0 one two three four. Wait, did I mess up index and row?

[01:17:49]I think maybe I mixed up index and rows and columns, right? Because here supposed to draw columns, but I'm index is clearly on a row, right? So, okay.

[01:18:04]Let's see if it's just something dumb like that. I mean, I don't There's still no 17 on the thing, right? Like six 12.

[01:18:12]There's only 14 in total, so it's still wrong. But, uh I don't Okay. Oh, wow.

[01:18:21]How? But I still don't get it. How do you even get 17? Even though if maybe we just counted the same thing twice in a weird way. I don't know. H but that's a silly mistake. Um but actually everything else I mean because it's n by n it doesn't actually matters uh on everything else.

[01:18:46]Okay but this is still wrong for case two. Again I'm still double counting somewhere. So that's still not great.

[01:18:53]Um, right.

[01:19:02]Okay. So, so four zero.

[01:19:15]The fourth column previous height is zero.

[01:19:24]This is wrong. I guess that's why. I mean, it's not wrong, but I think there's an imposition.

[01:19:33]That makes a double cap because I'm not differentiating between using zero and having z like no height.

[01:19:45]I I think so I'm off by one somewhere and it's probably messing me up.

[01:19:49]Okay.

[01:19:51]And that's why you know well I guess these things don't change but uh yeah okay that's true okay um the way that I could fix that though is just by in fact we we could just uh I mean I could just add an extra row of zeros or something. I think that'll probably be fine. Uh and then and we're going to do that. We're going to also add an extra column of zeros on the left so we don't have to do the awkward index minus one thing. Uh okay, fine. Right.

[01:20:37]This is so silly, but okay. uh and just go to uh this is I don't know why I would like this. All right.

[01:21:24]All right. Something like this. I don't know if it fixes it, but at least it makes things a lot easier than we realize. Okay. Well, now we're back to 17 again.

[01:21:33][laughter] Uh oh, I guess this is still awkward.

[01:21:46]No, this is not right for columns. It makes sense for rows because we're doing the same. But for columns, what my my code might have done is to um is to color it in. Right? So, um so, okay, but that's fine. We could just do this.

[01:22:04]Just start from the first column. Okay.

[01:22:06]The first one's still right. That's good. Uh the second one's still wrong.

[01:22:11]Not as good. But, uh but at least we can maybe take a look. Um I mean, that was definitely not um I mean, this is better, right? because now it is not matching anything, right?

[01:22:24]But it may also just be I do have this awkward smell that I know which is it tends height a the same way. So maybe it doesn't or maybe it shouldn't. I don't know. It's hard to tell the other one.

[01:22:36]Uh still the same. And that by the other one I mean like strictly higher. But I think like it just the other one just zoos out though. So I don't know that that changes anything. Um but uh but it definitely looks a little bit awkward asymmetric though. Uh but uh okay still on 107. Is it possible to get 107? I mean like just in all together right um but okay so 51 is 15 15 17 55 is 20. I mean, I guess that's possible, right? Because that's literally I'm putting the print up. So, that's less. This is just all the way up, right? So, that's good. Uh 4 Z is ping 30 is a little bit awkward, right? Oh, no. No. It's just It means that it can go all that. Best one though because four zero means that you have zero, right? So just 30. I guess it's either 30 or um what's that? 20. So I guess that's fine.

[01:23:57]One the two.

[01:24:01]I don't know how to debug this. Like I mean I'm looking at it and I'm sure we can trace it through but it's just very hard to uh go through it. Um the beauty of this. Oh, the thing this is so annoying because they made it um they made it n by n. So I was going to just remove the first column, but now I have to do like some weird thing.

[01:24:51]Okay.

[01:24:54]Okay. So this is still wrong. What I did is I think I did anyway is uh I made the first uh two columns empty. Actually, let's also make the last the third column empty. So then now we have a 2x5 or whatever. Now this should be a little bit clearer hopefully. Huh. But now this is right. So then what happened was that if I had this one here, it's wrong, right? So why is that wrong? It is wrong because it's wrong because you draw in the one.

[01:25:36]But if it tries to draw in the one, it counts the one somehow somewhere.

[01:25:44]Cuz in this particular case, there's no way to do both. You can't use that that uh middle one as a debug thing or you can't use the middle one without um with you can't do the one and 10 at the same time. I think is what I'm trying to say.

[01:26:10]Something is a little bit wonky here.

[01:26:21]34. What does 34 mean?

[01:26:25]Keep in mind that we we skipped the first column. So three uh the previous is one two three four is 45 35. So it's saying that it's all shade in you get the one. But if you don't get the one you 35, right?

[01:26:50]35.

[01:26:52]What does that mean? It means something is wrong.

[01:27:08]35.

[01:27:11]Wait, did I just do the math wrong?

[01:27:13]Maybe.

[01:27:15]19 20 30 No, the second row was 30 50, right? So, it's 50.

[01:27:23]Wait, is it?

[01:27:30]Oh, but you can't do the two. That's why. Um, okay. So, yeah. Uh, that Okay.

[01:27:37]I mean we see I think we found an obvious case where is wrong. So that's good. Um because it thinks that 35 we could do a one but that means that one the recursion is wrong.

[01:28:00]I mean F left is this way.

[01:28:25]F left makes sense.

[01:28:29]No. Is it I though? Is I + one, right? No, we're not enough. It's something like this cuz F left if it's match the same.

[01:28:45]Maybe I'm not doing it right because this inclusion it's a little bit awkward.

[01:28:59]It's something like this. I think I don't like the way that uh my thing is set up because if it's exactly the same, I think I actually uh just add one element because I think my for loops is one. So [laughter] because this should be zero but um the thing is that if is the same height this should be zero but this can never be zero right because we do a for loop inclusive loops right. So actually I've messed up here. Um well in this case there a lot of I mean okay I think I have diagnosed uh this is just wrong which is actually kind of sad but um well at least okay I mean maybe this is right but I think this is wrong because we don't I I didn't think about this part we Okay. So, we calculated. So, height cuz I'm like I I think I'm just like not matching them correctly. There's something like something like this for example maybe. Right. Um yeah. And it solve this one as a result. Um but I think there's also maybe um like this doesn't go to height maybe or something like that. Right. Um okay.

[01:30:24]Now it's too too small. But it's something um really basic like that.

[01:30:35]What the somehow this I mean I think this got fixed only because it got hidden uh or you know but this it's good that we have this case because still want to figure it out. Um, but again, this cannot be zero, right?

[01:30:52]So, that's definitely already a smell.

[01:30:56]Okay, so that actually fixed it. Maybe I just really bad at indexing. Uh, okay.

[01:31:03]I mean, I'm I'm not going to submit because we didn't we have to do the prefix something, right? But, uh, and that's not that hard. Uh, let's do it.

[01:31:19]Yeah, I'm lazy.

[01:31:22]No, not this. Uh, you would buy something like this. Right. Um I'm just double checking that these cannot be zero or whatever I for. So we have an extra row. Yeah, we have an extra row.

[01:31:53]That's fine. But please sum this be negative.

[01:32:10]No, because we have plus one on both of them. So I guess not. I just got confused. Okay, fine. So, uh return zero otherwise.

[01:32:27]Uh I think we we said that it was the wrong way. Wait.

[01:32:35]Okay. Yo, submit times out. It's fine. I'm just worried about I mean we'll figure out if it's time out but um if it's incorrect and just incorrect right we did it.

[01:32:50]I mean you wow I mean I I mean you don't understand. I am actually proud of this one. Um because I didn't think because this is hard. I mean, maybe we can up this a little bit more a bit. Uh, 6 seconds is pretty late. I mean, some of it is just like we can rewrite prefix some and that's fine. We can probably clean this up uh bottoms up. Um, and maybe we can uh No, I mean it's only 100, right? I don't know. And maybe you could um you could simplify some of this and ask whatever. I don't care. Right. We got it right. Um cuz I think the last What the What?

[01:33:39]Huh?

[01:33:41]I mean I actually was even faster than last time I did it. So uh I'm actually surprised. But uh what in the world?

[01:33:53]I don't know what this code is anymore.

[01:33:55]If I did, I would have, you know, just gotten it. But um yeah. No, I'm really proud of this one because I, you know, uh, we did it. And I think my logic is kind of sound. It's just kind of super ridiculous. Um, this is a an idea and a trick, if you will, that um that comes up very rarely, but I feel like I did it the other day.

[01:34:21]Um, so maybe that's just a little bit more fresh on my mind. The idea is that you do recursion for dynamic programming specifically. You do recursion in a way such that you're exhaustive. And the key part is just being exhaustive, right?

[01:34:37]Because in this case, for example, you're considering cases that are suboptimal, but you don't but you're trading that suboptimality in terms of uh uh com um in terms of I don't know uh uh for for dimensionality, right?

[01:35:03]And that dam dimensionality allows you to well just be uh off and faster. This is ridiculous. I don't know.

[01:35:13]Um yeah, I mean I the thing is uh you know now I want to do a recap but it's really hard for me to explain just the code, right? Like I don't like the the code is a result of all the journey that we've done. So you have to watch like I don't know like I I think even if if I explain it in a way that you understand it is it useful you don't know how to come up with it right and how to construct it. I don't know but you may feel better. I think that's the problem sometimes is that people uh feel that they understand and that's good enough but that's not your goal. Your goal is not to tell people you understood. Right? you watch these videos hoping to get better and I hope that you know you you figure out what I did but uh yeah um that's it. It's an hour and a half video on me in Sri Lanka when I should be uh I mean it's late so I'm not wasn't going to do anything but still should rest up so I could wake up morning early tomorrow but instead solving this ridiculous problem. That's all I have for this one. Let me know what you think. Thanks for watching. I'm super happy. Leave a comment. give me you have to give me some props because I am like very happy about this one and also like you know I I I'm not gonna lie uh like I I thought of cheating or or giving up just because this is my time off you know um I mean not I mean I'm time off but like you know like traveling and I don't I have very limited energy. So, please leave a comment, leave a whatever, show me some love and yeah, and let me know if you, you know, what do you think about Sri Lanka. Uh, thanks for watching. Stay good, stay healthy to good mental health. I'll see you later. Take care.

[01:36:59]Bye-bye.