Daily Leetcode : Jun 20, 2026 - 1840. Maximum Building Height

[00:00:01]Hey, hey, everybody. This is Larry. This is day 20th of the LeetCode daily challenge. Hit the like button and subscribe button. Join me on Discord.

[00:00:08]Let me know what you think about it today's problem.

[00:00:12]>> [cough] >> I don't know what that was.

[00:00:21]But, uh you know, hit the like button and subscribe button if you don't want me to die, I guess. I don't know. Apparently, uh uh don't know what happened there.

[00:00:31]But, uh yeah, let's take a look at today's problem. Uh I didn't do much today.

[00:00:37]I just went to the gym for a couple of hours and then watched, you know, the USA World Cup game.

[00:00:43]Um another World Cup games. I think one is still going on, actually, now that Um uh Oh, yeah, Paraguay-Turkey. Oh, someone got a red card.

[00:00:55]Anyway, um yeah, let me know in the comments who you are rooting for. Uh and if you have a secondary country, also let me know that, too. Cuz, for example, I'm >> [clears throat] >> Yeah.

[00:01:06]Those of you who watched me from the last World Cup, which is a long time ago now, um yeah, I'm a Messi fan, and so I I always root for Argentina as well because US is not likely to go as far. But, uh yeah, let me know in the comments. Anyway, you know, let's take a look at today's problem. We have 1840 maximum building height.

[00:01:27]Uh you want to build any new buildings in the city. There's the new building will be built in a line and are labeled 1 to n. However, the city restriction on the height of the new building. Height of each building must be non-negative.

[00:01:38]Okay. The height of the first building must be zero. Okay. The height difference between any two adjacent buildings cannot be one or cannot exceed one. Sorry.

[00:01:47]Additionally, the the city restriction on maximum height of specific buildings.

[00:01:51]These restrictions are given as two the integer arrays restrictions where restrictions ID max height indicating that building ID must have height less than or equal to max height.

[00:02:04]Uh so it could be zero, right? Okay. It It is guaranteed that each height will appear at most or that each building will appear at most once in restrictions, and building one will not be in restrictions.

[00:02:19]Okay, but you could build on Oh, no. I I I was going to say you could build on one, but I guess not cuz it must be zero.

[00:02:28]Okay.

[00:02:30]Um and I think the idea is kind of interesting. Um and we're trying to figure out what height we can be, right?

[00:02:38]And how many Oh, N is 10 to the ninth, huh?

[00:02:42]And restrictions Wait, what is N again?

[00:02:48]1 to N.

[00:02:50]Okay.

[00:02:52]The reason why I ask is because of this thing.

[00:02:55]The the length of restrictions only goes up to 10 to the fifth.

[00:03:04]I guess that's fine, actually. For some reason I don't That's why I looked it up, but I I I forgot whether this is like a mapping of index to whatever or the X to that, right? Okay. IDs unique.

[00:03:17]They're at least two Oh, no. No, the ID numbers at least two goes to N. Max height goes up to 10 to the ninth. Okay.

[00:03:24]So, the first thing you want to do is probably just sort sort is cheap, sort is easy.

[00:03:28]Um just because then now you have you sort them by ID, right?

[00:03:32]>> [cough] >> And then let's think about what we want to do.

[00:03:37]Um and I'm just drawing uh or bringing up um the drawing thing so that I can Well, just draw. Hang on.

[00:03:51]All right. And then the idea here is that we just have some constraints.

[00:03:58]Right? And the thing about these constraints, of course, is just that oops.

[00:04:06]These constraints are What was I going to say?

[00:04:08]Oh, only Mhm. Oh, maybe that's not true. I was about to say that only two adjacent constraints matter, but that's not true, right? Because you can have something like this or like I'm I'm writing that as a constraint. Like Like maybe this is the constraint for this one, and then you have constraint that's here, and then maybe the next one after that is here. Well, technically, your constraint would You have to You can only go up to here or something like that, right? Depending how you want to draw it or, you know, and then otherwise, you just go up, and then uh Does it Does it have to end at zero?

[00:04:41]Doesn't seem like it, right? I'm just looking at the examples. Seems like you'll just keep going. So, actually, in this one, maybe just keep on going forever, right?

[00:04:50]>> [clears throat] >> Yeah.

[00:04:53]Um Yeah. And then, the idea here is that you have this adjacency thing is greater than one thing, right?

[00:05:03]So, then, what How do I think about that? I think in that sense is they're not real constraints, right?

[00:05:10]Or sorry, maybe I'm not I I I'm not using complete sentences. Meaning that slope greater than one Oh, not this one.

[00:05:16]Sorry. Uh I'm really confusing on my way. I mean, this one, right? Like the next thing maybe greater than one. If it's greater than one, then it's not the real constraint. You can maybe even cheat and put a fake constraint. In terms of implementation, maybe that's not necessary yet to talk about, but but right?

[00:05:33]Um Or, you know, maybe if you had something like um like here, right? Then you would just go straight to here, right? Or something like that.

[00:05:44]Um and the real constraint would be here, maybe, or something like that, right? My I'm just trying to think.

[00:05:49]Um Yeah.

[00:06:07]And then the max is either obviously at the end somewhere up there, really. Uh or somewhere in the middle, like in this one, right?

[00:06:17]Um because you go up as you can and you go down. Maybe there's some formula and it could be flat anyway, so you don't have to be precise, but um I mean, but that formula we could figure out. Is that enough?

[00:06:48]I guess the tricky thing is um try to do it in n well, n log n now because we sort it anyway. Time where like if you have a lot of these these random constraints, how do you know that like you know, like this one goes here or something like that, right? Well, technically maybe it doesn't have to be, but it goes do do do do do or something like that, right?

[00:07:12]Um So, what does that mean?

[00:07:20]Right?

[00:07:22]Is this a stack problem?

[00:07:26]Cuz basically now if if a constraint doesn't matter, we could remove it then now cuz we only look at it. Okay, let's say we're going from left to right and I just need to try to figure out the problem. Let's say we're going from left to right.

[00:07:40]Um yeah, we first pass from zero to the next one, we put a fake cap or whatever.

[00:07:47]And or that it doesn't even matter cuz then it's not a if the cap doesn't apply then it's not a cap.

[00:07:54]If it's What if it's too low? If it's too low then we just do do do do do do and then this is the new cap, right?

[00:08:02]Do we even need a stack?

[00:08:05]I'm not sure because then here we just kind of ignore it.

[00:08:09]All right, cuz cuz the then we just set this as the cap, maybe?

[00:08:15]I guess you can do that, right? Cuz here um cuz it could be possible that it's here, right? And if it's here um I don't know. I'm trying to I'm trying to think of a case where you need the the actual path a little bit more.

[00:08:38]Like Like I'm trying to think something like I don't know. Is there a way such that you can you have to force um like maybe it goes here, but then because you have another one that's lower, you actually cannot go that high so you go here, right?

[00:09:02]Instead. Then this is the peak.

[00:09:05]Maybe something like that. I'm I'm not drawing it quite precisely, but that's kind of the idea. And again, they don't have to be next to each other anyway in terms of Huh.

[00:09:19]I'm drawing a Right now I don't know how to do it yet, by the way.

[00:09:23]Um Or rather, maybe I have some ideas on how to do it, but I'm trying to think I'm trying to you know, use these examples to kind of feel out the invariants of what I need to do cuz I don't want to, know, implement it and then be like, "Oh, yeah, this one."

[00:09:40]Okay, so then what happens? This means that if we do a fake top thing, that means that this is constrained, but then we go here, but then we would only look at this way. So, then now we need we know that uh this is too high, then we have to go low. So, then what does this mean?

[00:09:59]This means that we just say, "Okay, this is no good." Then we have to go back and then do this thing, maybe.

[00:10:05]Um and then >> [clears throat] >> Would that only Would we only ever pop once?

[00:10:15]Would we ever pop more than once?

[00:10:17]Because if we would pop, we would have popped earlier.

[00:10:21]Right? I mean, obviously, if we keep track on a stack, we don't keep track of random stuff on in the mid in you know.

[00:10:28]But do we ever pop more than the top element?

[00:10:32]Like, do we ever pop this thing?

[00:10:35]I guess we could, right? Because then now um No, because if we have a thing that's higher, then it would have already been popped by this one, right?

[00:10:46]Am I wrong?

[00:10:48]Hm?

[00:10:49]I think this is one of those things where now I'm like, I think I have a general idea about it, but also honestly, I do not know how to I don't have all the edge cases right or right.

[00:10:58]I don't have all the cases um shaped out. Um and I would like to instead of you know, uh um uh instead of kind of just winging for the edge cases, which maybe is a good idea, to be honest.

[00:11:11]Um maybe it's just worth implementing some stuff and then kind of see play around with inputs that way and then see if it it matches my assumption, right? Um it's it is way annoying though, this problems uh in terms of implementation. So, we'll kind of go as we need. And really, 10 minutes in, wow.

[00:11:30]Um Hm.

[00:11:45]Let me see.

[00:11:48]Hm hm.

[00:11:57]Okay. So, let's let's get started, right? So, then Huh, I'm wondering Right now I'm [clears throat] just thinking about sentinels, right? And maybe we could just write um We start at one, I guess. So, restrictions. append maybe zero uh zero or one zero.

[00:12:21]Yeah, okay, fine.

[00:12:22]I I don't I I try to avoid um one index things when I can, but maybe it's fine. Then n Uh is there one on n? I guess so.

[00:12:33]Maybe we could do n plus one then.

[00:12:35]Add um Add infinity, right?

[00:12:40]>> [cough] [clears throat] >> So, we never constraints. Oops.

[00:12:45]But uh yeah, okay.

[00:12:47]So, then now uh let's see, right? So, then now I I I I don't know. I guess we do need a stack. There is some Um There is some intuition there.

[00:13:09]Right?

[00:13:11]Um And now for what's it? ID or X? It's ID, right? And then Y is the thing of the height and restrictions.

[00:13:21]Um And now we just compare My thing is also one is the simulation, right? But then setting it up. But then how do you keep track of the highest height, right?

[00:13:35]Because as we said, if we pop things off I guess we pop things off then we have ignored all that height. So then stack maybe instead of just containing I was originally going to write maybe XY or maybe write XY height under the stack.

[00:13:53]So then So then the stuff that survived all the way to the end we just take the maximum height.

[00:13:59]Height is the H is the maximum height from the previous like like the the best height that goes up to this um segment, right?

[00:14:12]Um Okay.

[00:14:15]So then now restrictions and now if length of stack is equal to zero, I mean we could have written this a little bit cleaner with this and this, but it's fine.

[00:14:24]Um then stack.append uh XY0 maybe in terms of heights. I mean I guess it can never either it can ever actually be zero.

[00:14:40]Um uh in terms of like it wouldn't it would never be Oh, I guess it could be zero if if like, you know, the restriction is zero, right?

[00:14:58]Yeah, if the max height is zero, but they would never be zero like on other cases. Okay, so then now we want to check the previous stack, right?

[00:15:10]And and maybe, you know, I I just like writing while loops because it you know it feels intuitive.

[00:15:20]Or like if it's true, it's true. If it's not, it's not, right?

[00:15:24]Okay. So, then we write um previous X, previous height restriction, and then the previous height. Oh, that's not hm Oh, okay.

[00:15:40]Yeah, okay. I was going to say that H is is the height, but but that's not the height in which you passed the X. But I guess that's the Y, right? Cuz you always want to be at a restriction at the restriction height.

[00:16:04]Yeah.

[00:16:09]I guess this in that sense is actually is zero.

[00:16:14]Lieutenant D. I mean, I I said it anyway, but I want to make this more explicit, right? Because Yeah, okay. So, then you have this is equal to stack the top of the stack.

[00:16:26]And then now we do some maths, right?

[00:16:29]So, hm if Y minus PY Actually, I guess maybe I should do this first. I don't know.

[00:16:46]And also, this should always be true just from this.

[00:16:49]Um so, we we we remove this for now. So, okay, if is greater than X minus PX, that means that the thing is greater than one, then this restriction doesn't matter.

[00:17:07]Limited by the previous one. So, then we just continue because we could skip it.

[00:17:14]Right?

[00:17:16]Um else >> [gasps] >> than now it means that this would be the new restriction.

[00:17:30]Right?

[00:17:35]Oh, I guess this is should be absolute value.

[00:17:39]I I was I was Yeah, I was just like in my mind going a little bit like I'm I feel like I'm missing something. But uh yeah, I mean this this will be positive, so I guess we don't need absolute value here. But obviously you cannot go down as much either.

[00:17:53]Um No, no, no. So, this is wrong then, right? Actually.

[00:18:00]This is actually not This is right. This is right.

[00:18:03]>> [laughter] >> Um >> [cough and clears throat] >> Um because it because I I'm just trying to think for the cases, right? So, if um if this is higher than the the slope up, then then this restriction doesn't matter. But if it's lower then it does matter actually. Then this is the new restriction, right? So, yeah, if um Uh how do I write this? If Y minus PY of the negative version of this is greater than X minus PX, and I know that I could have written it the other way, but I think this is more clear to it is more direct with the intent of of what I do, right? So, this does matter.

[00:19:02]So, then now Okay, so what happens if it's in the middle?

[00:19:08]I'm just trying to think through.

[00:19:10]If it's in the middle, it does matter.

[00:19:15]But in a It does matter, but Yeah, it does matter, but it doesn't change the thing, I guess. That's That's what I want to say. Um And what what I mean by that is just that Um let me bring up the drawing real quick. I'm just going for the cases. I'm I'm not really doing anything like I know that I'm not drawing much. But basically, if like you know, you have this is uh XY you goes Y slope a one-to-one slope.

[00:19:49]If I had here, right? If If this is my previous one and this is my previous one, well, then this What I'm saying is that this restriction doesn't matter, so we could ignore it, right?

[00:20:00]Um if if it is here, then this restriction matters, but but this restriction still matters as well, I think.

[00:20:10]Maybe I'm wrong.

[00:20:11]But, you know, you could just do it this way, right?

[00:20:14]Um do I remove this actually? Do I pop this?

[00:20:18]Maybe I'm wrong. Maybe I don't need this.

[00:20:24]Because here would be the cons- new constraint anyway.

[00:20:28]Hm.

[00:20:31]Oh, what the Oh, I could say back then.

[00:20:34]Um and then the other one is um if we go the other way, right?

[00:20:39]And I I can figure out the other one, but these are the scenarios. So, you have here. So, then if you go here, then obviously, well, actually, we do have to get rid of this to kind of uh draw a better line from the previous whatever, right?

[00:20:51]So, we have to figure out how that works. But we're here, then we can actually just go to do do do do, right? So, So, we So, we could definitely do it. And then maybe this is the new constraint and this is not used anymore.

[00:21:04]Um maybe I have some What What if we go somewhere really down next?

[00:21:09]Um then now this definitely needs to do that. And then now we have to do the math for this one. Oh, I guess then we we don't delete this one because here we have to do the math for this one. It may not We might have to pop again, but but if we have something more in the middle, like say here.

[00:21:28]Or even just like directly if we have one here, right? Then now this goes directly up and then we pop this, but we we keep this, right? So if it's in the middle, we do keep this.

[00:21:39]Uh no matter what, and and and this is the stuff that I'm talking about with case analysis, right?

[00:21:45]Um and then if it's really low, then we have to get rid of this Well, get rid of this one and then have to figure out what the previous thing is so that uh we just keep going. Like it may be for example, it could be here. If it's here, then it just go you know, we adjust to something.

[00:22:01]Uh okay.

[00:22:02]So I think I understand this now. It may not It still may not go for all the cases and it might still be wrong, but I think we have an idea of what we want.

[00:22:11]Um and uh maybe this needs to be a while loop.

[00:22:16]Um honestly, I mean that maybe not this because it doesn't matter.

[00:22:20]Or my suggestion And I'll double check if it goes up.

[00:22:25]Okay, so what It doesn't matter.

[00:22:29]Um limited by the previous one. Okay.

[00:22:32]But here it does matter.

[00:22:36]We have to um get get the uh highest point of the gap.

[00:22:46]And then um And then that And then we push. I I guess that's the thing that I'm going to push the stack. Right? Stack that append uh X.

[00:22:58]We always end it Y because if it mattered, then the Y matters, and then we have some like new age, right?

[00:23:06]Uh and then age is just equal to some maths.

[00:23:10]Uh how do I do this maths? This is the maths that I'm going to get some water real quick. Hang on. But uh still thinking. Just you know.

[00:23:19]Doing maths.

[00:23:20]Am I doing maths or am I breaking?

[00:23:21]Probably not.

[00:23:23]But uh I'm just going to get water. Talk about it though.

[00:23:27]Uh okay.

[00:23:28]Um Okay, this is where I do need some visualization again.

[00:23:34]Uh okay, so this is the thing, right?

[00:23:38]Um let's see. What does this mean?

[00:23:41]So, we have X.

[00:23:45]But DX we have DY.

[00:23:50]So, then we use DX Well, we use like DY portion of it on DX. And by definition um maybe this is the wrong place, actually.

[00:24:02]Oh.

[00:24:03]I think I did it in the wrong place, but it's fine. I'm just looking at the code and I think it's the wrong Whatever. I'm I'm doing the one in the middle first.

[00:24:10]But uh yeah, if DY, that means that DX is greater than DY.

[00:24:15]And as a result, DX - DY is equal to the extra extra you go to this, and then extra divided by two is going to be the max height, right?

[00:24:27]Okay. Seems pretty not bad, right?

[00:24:30]Okay. And I think I this is not the right place though. What I mean is the else of this. So, if it's not this and it's not this, then it is going to be else. So, actually that's what I actually mean.

[00:24:42]Um So, now at least we figured out the math.

[00:24:46]Okay. I mean, we still have to fill this in. I just haven't done it yet.

[00:24:49]Huh.

[00:24:50]Else it is in the middle or something, right?

[00:24:55]Uh so, then we'll just write it that way, right? So dx is equal to Um, x - px, dy is equal to y - py. We probably could substitute some of these as well, but whatever for now.

[00:25:09]Uh, we'll we'll just do this.

[00:25:12]Um Mhm.

[00:25:27]Yeah, okay. Um So, uh, I guess we have to assume I just want to assume that this is true um, for now. Then now it's going to be dx - dy divided by two. That's going to be delta height.

[00:25:47]And it's delta height of it's the height of what was higher, right? So, h is equal to max of y, previous y plus delta h.

[00:26:03]I think that's right, maybe, right?

[00:26:08]Um, otherwise, this does matter get the highest point of the gap. Uh, maybe I should just move this up. Seems like we use it in places. Let's actually update these then.

[00:26:19]I took the water and I didn't take it.

[00:26:36]Um, okay. So, maybe this is the only one where Mhm.

[00:26:42]This this is where we have we write like maybe while true.

[00:26:48]Um, because then we want to pop it, right? We want to pop the previous one.

[00:26:53]Uh so mhm How do I do the math?

[00:26:59]>> [sighs] >> So, okay. So, if negative D So, this is way under. So, then now um Actually, now it doesn't matter, right?

[00:27:21]We don't need to do the math for the one we're getting rid of. That doesn't make sense. Okay.

[00:27:31]Um I might have to change some stuff, actually, cuz I I Otherwise, we have to rewrite a lot of these same things, right? So, then we just do stack.pop. I think that's it. Maybe I'm just being because we don't have to care about that one, and then we have to do it from the previous one, right?

[00:27:51]So, yeah, maybe that's it. Maybe we have to write like while do do do do do, right?

[00:28:03]And this is not continue anymore. This is a break.

[00:28:09]Um and then you have this stuff.

[00:28:14]And also break. I mean, it it it's a control loop is a little bit weird, but um but I think that's mostly okay, right?

[00:28:22]Maybe?

[00:28:24]Uh and then here we Oh, well, we turn negative one for now. I just want to print the stack, and I just want to run it real quick just to make sure it doesn't infinite loop or anything weird.

[00:28:32]Um okay, it doesn't infinite loop.

[00:28:34]That's good. And also, if I look at the max of the last element, I mean, this is like a one-line code. Like, that's why I didn't write it. Um oh, um that's actually weird. Or maybe not weird, but just surprised.

[00:28:48]Cuz Oh, cuz I put that this restriction doesn't matter limited by that previous one.

[00:28:55]Okay, so we don't do that. So, my sentinel is useless because it just gets ignored by definition.

[00:29:02]Um Maybe I don't need this then.

[00:29:08]May Maybe I do need an extra um thing of um the height of the last element.

[00:29:28]Mm.

[00:29:34]Yeah, okay. I'll try to think maybe I could could do something funky, but but maybe it's not really worth uh like for to to keep the sentinel.

[00:29:45]But instead, um the top of the stack is the last element, right? So, we have PX, PY I don't think we need PH as you go stack.

[00:29:54]And by definition, there will always be one element just because the the sentinel element would never be removed.

[00:30:02]Yeah, cuz you can't go under it. So, then now we have N Yeah, N is the last element and um Yeah, DX is equal to N minus PX.

[00:30:23]So, then DY is equal to DX.

[00:30:27]Cuz we just go as high as we can. So, then we just go to previous Y plus DY.

[00:30:32]We can print it. I mean, it's just for And then we could just whatever about it, right?

[00:30:37]So, this should print five, okay. Right?

[00:30:39]Should print to I mean, this is clearly wrong cuz there's a six here.

[00:30:46]Right? All right, let's let's actually connect them together because now now we're tracking too much and I'm just being lazy for some reason, right? So, uh best is equal to p at y plus dy, so that's from the last element. And then for um whatever whatever h in stack, best is equal to max best h. And then just return best. I mean, I know that's wrong for the last one. Is there anything funky about it? I guess it's the only one that's normal.

[00:31:12]Maybe I'm just off by one in how I do the the math on the the five. Um Yeah, okay. Let's actually print the stack though. I still wanted to print the stack, but I forgot.

[00:31:26]Um okay.

[00:31:29]So, at 10, it thinks between seven and 10 I could go to six. Why? Cuz four and three has has three.

[00:31:42]Huh, that's weird.

[00:31:44]Cuz dx is three. dy is one.

[00:31:50]Oh, I see.

[00:31:53]I I'm just being dumb because it went down.

[00:31:56]Um So, cuz d y can be negative.

[00:32:03]That's why.

[00:32:07]So, this is actually absolute value.

[00:32:08]Okay, that's Okay.

[00:32:12]I thought something was weird when I was typing it out, but that's why I was able to find it so quickly, but I just I don't know. I just forgot. All right, looks okay. Am I right? I don't know.

[00:32:24]Uh let's YOLO submit.

[00:32:27]Ooh. I I'm not going to lie. I am honestly a little surprised. Not that I'm not confident, but sometimes I don't know. It just feels Oh, and the code doesn't look very clean either, but uh Look, I went correct, I'm not going to lie. Um I'm not going to complain too much, but I wasn't I I was not super confident about it. I would I would say if I had to guess uh a number, I would say 50% I would have gotten it wrong. Uh like I would have bet on myself being wrong, but uh not wrong wrong, just missing a a minor detail here, like like missing this one. I would have honestly would have missed this one if that wasn't an example with three, you know? Um so I I wouldn't be surprised if something like that where I just kind of missed you could say missed a case or missed like just thinking about it or whatever, but you know. Like this has that kind of feel. Um yeah. I guess that's the idea about these stack problems is just um kind of thinking about invariant and whether you you need to look back more.

[00:33:30]I think one thing that I maybe didn't mention is that N is Well, this is this is N is 10 to the 9, but what I meant is the number of restriction is 10 to the 5. Um so immediately means you cannot do N square. Um we have N log N anyway, so we can do N log N or we are going to do N log N. Um so stack kind of makes sense.

[00:33:49]Maybe this >> [clears throat] >> um Um and that's where I was trying to play around with invariants because um the idea here is that um I guess I didn't go I didn't talk about this explicitly, but I did mention a little bit is that I was trying to figure out specifically um if only two adjacent restriction is enough, right?

[00:34:13]Um and I was even trying to figure out like do I need iterated, but um and here it kind of made sense after I coded it out. Um Bec- But it is still true that you only need two adjacent. It's just that you need to pop them. And once you pop one, you never do it again. Um that that's the kind of idea that you need for a stack is that once you realize you do not need a restriction anymore, you never need it again in the future, right?

[00:34:43]Um, which allows you to save space, um, and you can say that um, and you can write this a different way, actually. Like, you could write this as always append, and then just um, pop in a couple other places instead, uh, maybe. Maybe not, I don't know.

[00:35:00]But, that's it.

[00:35:01]That's all I have for this one.

[00:35:03]Uh, let me know what you think.

[00:35:05]Thanks for watching. And, yeah. Stay good, stay healthy, take care of your mental health. I'll see y'all later, and take care. Bye-bye.