Daily Leetcode #2251: May 30, 2026 - 3161. Block Placement Queries

本站添加: 2026-06-01

[00:00:00]Hey, hey everybody. This is Larry. This is day 30 of almost the last day of the Leo made challenge. Oh, we have a hard one. Hit the like button, subscribe button, drop me a discord. Let me know what you think about today's problem.

[00:00:13]Uh, what did I do today? I guess I just went to the gym and then ate a lot and then worked on random things. Uh, let me know what you think. Hit the like button and subscribe. Did I say that already? I am having brain damage. But in any case, uh, yeah, let's take a look at today's farm. We have 31 161. It's a hard, so we might as well get started early. So, I do have a I'm volunteering for a race tomorrow, so I have to wake up a little bit earlier, but that's okay. I just have to make sure I know how to get there. Anyway, let's take a look. 3161 block placement queries. Uh, and if you're with me the entire month, well, I give you a congratulations. We're almost there. Um, and yeah. Okay. Does an infinity number line origin at zero extending toward positive x?

[00:01:02]Uh I mean is it infinity if it just goes in one direction? The answer is yes, but still kind of awkward phrasing.

[00:01:10]Uh but okay, so you're given 2D array queries which contains two types of queries. Uh for query type one, build an obstacle at X. Okay, it's guaranteed that there isn't one before. Okay, for a query of type two um x and size check if it's positive place a block of size in anywhere such that it is okay such that the block entirely lies in the range o x a block cannot be placed if it intersects intersection but may touch it no you do not actually have to place the block okay queries are separate okay I mean I think this is relatively straightforward maybe maybe not I don't know at least idea because I feel like recently anyway and this is why I talk about practice a lot. I talk about it a little bit more in the contest videos because they challenge me a little bit more or at least the difficult the difficulty is a little bit harder, right? So, it's easier to make mistakes.

[00:02:08]Um, but this is why I talk about practice a lot is that um there are a lot of things where um you know, you may save one minute here and there because you're like, well, you're just thinking to yourself, I know this thing or I think I do. I have to prove it. Is it true? Is it not? you know, and you just kind of go back and forth and even like in a very short uh component, right?

[00:02:29]Like like a hard problem sometimes of like two or three or even more components, right? Um so um so yeah, so if each of those components it takes you an extra minute, that's already five extra minutes. And then now maybe if you do it on Q3 and then now Q4 you you you already waste too much time and you barely missed out on solving it or something like that, right? So there are a lot of stuff that can happen uh like that, right? So definitely um yeah so definitely that's just a thing, right? Um my hair's funky, isn't it? Um so so my point is that uh when I find myself rusty when I find myself I'll practice that's where these silly mistakes come from. That's where I'm like I think this is right but I have to like kind of prove it. I mean obviously for these daily videos I do try to articulate more and I am talking more and as a result I do make others type of silly mistakes because I I'm like oh I have to note this thing but I just forget by the time I implement which happens. Look I can't juggle that many things in my head and talk about it at the same time. There are people who are very smart and can but I am not anyway.

[00:03:41]So this one you just try to figure out okay uh is there a size or you know from zero to x right and and yeah I mean it goes to infinity so the I think the idea here is just um going to be binary search is the core idea of kind of finding a thing but it's just also just maintaining all the blocks in some way or not all the blocks all the obstacles sorry um but not even the obstacles but just the size of the blocks that are possible and then it's just a lot bookkeeping. So that's my initial um idea and I don't think I'm going to be wrong on that one. Uh it's just you know I mean when when you have things that are mainly bookkeeping uh and when I say bookkeeping it's just about um you know you have some invariance that you keep every step of the way and there a lot of maybe links from different places and you have to maintain them in the same uh uh so that at the end the invariance still holds right so a lot of bookkeeping but but it's going to be right because the the the uh I mean well it's also possible that I misread some forms because that happens sometimes.

[00:04:47]But aside from stuff like that, um, you know, when you think, okay, well, it's going to be log, it's it's not going to be that much of an issue because login is really fast, right? So, okay. So, so I have so my idea if you think about it or if I'm thinking about it and maybe something that I would you know um how to say it like if it's something that I like write out a spec doc for for quad code or some chat GBZ to write I might write something like okay well um what I want to do and this is maybe more than I would anyway because people just cheat and copy and paste but but what I mean is that you try to write out like a little bit of implementation spec X maybe I would think okay so we need so we're having like a query pattern right so I I need to have two things like one is size of the not I keep saying I keep saying blocks but I meant like size of the spaces or blocks of spaces maybe right um and maybe I'm really wrong by the way but this is what I'm thinking of right um and And um there may be some sort of um so that that's for uh I mean this is I don't know maybe the numbers are wrong but uh but this is my exploratory thing of like okay we guess we need um so for query one or query type one sorry type one um you know my idea would be that okay we start with an infinity block. I mean it doesn't have to be actually infinity but like you know effectively infinity a big block and then split it into pieces right um and then maybe for for T2 as a result uh for the query for oh I think I mixed it up but yeah and then now for T2 we just well we could really get the max of some some portion right so maybe just like okay some sort of range max query right which you know in this case it's not even just range it's prefix max query right um sorry got to hydrate a little bit but that's kind of the idea right and and knowing that we have to do this then we we're already thinking of okay well there's some data structures that we can think about we could think about uh you know segment tree maybe segment tree we can think about and this is prefix right so maybe some kind of binary index tree right or fenick right um and then there's another thing that you know I'm already thinking about is okay well we only query up to x so we might need to split them up right or like maybe not splitting up I mean just splitting them up but maybe more specific like logic to figure out how to split things, right? And what I mean by that is that okay, let's say you let's say you have a you have a a block that goes from my is my window showing I'm just double checking. Okay, it'll be really sad because I I keep forgetting to recording sometimes. But yeah, so let's say you have a query that goes from um you know of type two of goes up to 10 and you want like eight and then you have a thing at um three. Well, then now you have two blocks of an obstacle at three. Well, you have two blocks. One one empty block that is length three and then the other that goes to well maybe infinity but infinity minus three say.

[00:08:40]And of course then now you may say well we have a block of infinity minus three.

[00:08:46]That should be good. But now you just have to do some maths to kind of like you know make sure that no no we cut off at 10. So the actual space if we cut it off at 10 um it's going to be seven.

[00:08:56]something like that, right? But you know, we just have to kind of consider stuff like that. But but um you know everything here nothing is blocking because it's just about keeping track of stuff and um uh keeping track of stuff and also everything is at most login is what I'm what I want to say right like here like these two things are login and this is maybe binary search and then do some mixture of one things if statements right So as a result like I you know I haven't really looked at the constraints. Um yeah I mean I I don't know but yeah um so yeah so that's basically the idea and that's enough for me to kind of get started on right. Um okay so h how do I want to write this?

[00:09:55]So then we do want to keep track of obstacle. Maybe we could keep track of obstacle in a sorted list.

[00:10:00]Right. Um and then maybe like uh some sort of range max segmentry. Um maybe right. Um yeah, I mean I I'm hesitating only because I um because for for these videos I really do not like um I don't know just copy paste in code but segment tree if that's the case. is I mean you could I'm trying to think maybe I can use just binary index tree but either way like I'm just trying to think like what's the or are there alternatives um uh whether the alternatives because I don't know I just don't want to explain segment tree or fan tree to be honest I'm not going to lie um that is a lot of the motivation of me just thinking about But um I think suffice to say at this point because you can do a segment tree video that takes like two hours maybe a shorter um and you know so I'm not going to go over segment tree in this video but I just want to go you know if you want something to Google on or chat GPTR on search up on segment tree max um and maybe specifically um range query point update right so something like that Right.

[00:11:34]I don't think you can actually do binary index tree because of the point update um because we're up going down. But these are things that we were thinking of, right? Um but also like I I kind of knew that you could do segment tree and binary index tree. Binary index tree generally has a lower constant but a lot more nuance to make sure in terms of invariance and stuff like this, right? So okay, so this is what you want. Um I'm going to label this as prerequisites.

[00:12:06]So definitely I don't know search it out at least in my solution, right? Maybe there's a really simple solution that I'm not thinking of and then well my apologies and then you know you can watch it and you can maybe watch the previous time I solved it and maybe that's a little bit better as well. Um but uh yeah so this is the prerequisit.

[00:12:25]Um I am going to f I do have I think I have something implemented somewhere.

[00:12:30]Yeah. Okay. I have this thing right. Um and this is something that I implemented a long time ago besid that I copied it from chat a long time ago. I don't remember anymore. It's just in my past in my my stack of things. Um and then this one actually it is already max. I lied. I was going to say cuz you I thought I had a adding version but no this is a max version and updates range right okay I have to double check uh the I always forget the parameters I should actually put the test parameters here because there are two ways to write segment trees or there more than two ways but but the the big critical thing is whether um you're a a 2x plus one guy or 2x guy or zero index or one index maybe is another way of saying it. So and and I always forget and this one as you can see is actually one index because uh left is times two and right is times 2 + one.

[00:13:32]The one the zero index version is 2x + one on the left side 2x plus two on the right side right and that's just some some stuff. Um but yeah these are these are things that you know it is what it is. I don't know right anyway. So then yeah uh then now we have let's just say s max maybe I don't know naming things is hard s tree I just call it s tree right except for number of elements uh what is m oh m is the initial thing I don't know I don't always said this but um okay fine um yeah so here we want to know uh how how how what is the size of the segment tree right well the segment we want is actually over the number line, right? So if it's over the number line and maybe this part I should have uh checked for which is x. So I lied a little bit because it's not log n is log of the range of the numbers, right? And thankfully this only goes up 5 to 10 * 10 4th. We can actually probably just look up uh like the max of all the type two queries because we're given it and as a result then we just take the max of that because we're not going to get queries more than that, right? So maybe we'll do that, right? So for example M0 so for do for um quer query in queries um you know if query sub zero is equal to two meaning that is type two then m is equal to max m query sub one right because that's the x that's the most you're ever going to look right everything on the you know and then maybe at the end I don't know I always like to do something like this just because I I'm really bad I just divided by some really small number. Five is probably just a totally random number, but I mean it's the same random number that I use a lot. So, uh I don't know if I but yeah, we set m is m and default just set everything to zero, right?

[00:15:32]And then now um as we said, we want to initialize with an infinity. Um in this case, we'll have infinity is equal to I don't know 10 to the 20 doesn't really matter, right? So then now we can say obstacles.

[00:15:46]Um yeah. Well, I I guess it doesn't really m um maybe we could add one at zero. I I don't think would you add one on zero? Yeah, because it starts at zero, right? Um it's just I'm trying to think whether you need this placeholder. Um maybe you don't but it makes some stuff later on a little bit easier because you have this invariant because if you do a binary search and nothing comes up then well zero will always come up is my point and so you could do you know um like the math makes it a little bit easier. And then now we just update um and I I really should label this. See if it was chatbt it would have the comments. So maybe I should actually ask chat to give me comments but okay. So, um what is I always forget. Oh, I is the node. So, that's just one. Uh this these are the ranges that we care about. So, that's going to be one. And so, yeah. So, we update. This is very awkward looking as a result, right? Um I think it's this anyway. I could be wrong actually. always forget if it's m or m minus one. Uh and then position. Uh so we set the I'm signing because I think this is one index and as a result like because we set a thing at zero technically speaking um I think I think only this node matters so may maybe not m minus this one and then we update zero. We set it to infinity, right?

[00:17:41]Um, I'm going to just run it real quick just to make sure that I don't get any weird um like combination errors or whatever it's called or like I mean I know in Python I know it's Python it doesn't actually compile but sometimes it just runs into weird code and it it chokes right okay so then now this is our our initial state we have an obstacle zero we have a segment tree set and infinity right so then now we can start the query so for query and queries we have type two types what do they do again uh if query of zero is equal to one. Then we have um well just this right um then we build an obstacle and what how what does it means to build an obstacle and this is where I was talking about earlier with um with uh whatchamacall with bookkeeping right because now we just all we have to do here is just say obstacles add um x right you know but then now we have to update um and maybe I needed more things to be honest But um but in theory that's all we need. But what we actually want is to uh binary search because I mean this this part is true but we have to figure out how to do segment max. Right?

[00:18:52]So then now we have to binary search the segment that it belongs to somewhere like this. Right? Is it left or right? I guess it doesn't matter because um it doesn't matter because two of them cannot be like the X all X's are unique in the pricing of of query type one right so it doesn't matter if it's bisect left or bisect right okay so then now we have index is equal to this so then this goes to the next obstacle right so that means that um um yeah so then this is Okay, maybe I should put one at infinity too. Actually now that I think about it that's why because here I'm just thinking about the invariance and well this can go like for example the first one it would definitely because you have zero your binary search the index will be outside the bounds right so but we add um at infinity maybe that's a little bit cleaner right um because then now you have two bounding obstacles um right and then now here that means that this will always find infinity the index of that right and then now previous p index or previous is equal to index minus one and both of these will always exist, right? Because bisect left will never reach zero. So that this will always be at least one and then this will be well index minus one, right? Okay. So then now we have the the length of this, right?

[00:20:27]So now we have the length um right and this length h by convention we stored it at the beginning I think I mean by the way and by I say by convention but just however you want to keep it consistent right so that means that um yeah okay L is equal to um obstacles of index minus obstacles of P index, right? So this is the length, right? So that means that sigmax and and you know when you're playing around when you're coding and you're testing, you can actually um um you can actually um whatchamacall uh uh add assertions to test your things, right? And here because what I want to do is you know um how I wanted to do my storage and maybe I should have explained this a little bit is that let's say you know we have actually let's go here right so here we have three and infinity minus three um where we actually store this will be three at index zero oops three at index zero and then at index three we store infinity minus three so that is from that point forward or something like that, right? Um, so that's going to be what the convention should be, maybe. No. Yeah. Yeah. Yeah. Starting at three, right? So, so that's kind of how I'm how I'm imagining it.

[00:21:59]I Okay, we don't need I'm going delete this.

[00:22:04]Um, let's delete this. All right. Take screenshots if you really care about it.

[00:22:12]Okay. So then now, yeah, we can just do the update, but if you're a little bit non-confident, right, you could do um max is kind of weird functioning, but uh oops, you could just um assert that um I always forget the the syntax. So okay, so I is always going to be one because it's one index and then for range, right? So okay, so it's going to be one uh zero n minus one And then um we want to just search for um X. Is it X? No, no, no. It's obstacle or P index, right? P index. So that means that the previous index, right? So um so we're only looking at the max from one element, right? So we assert that this returns out. I mean, of course, uh, this this has a time penalty, so you don't want to leave it in the real code, but you want to make sure that your your um, you know, if this fails that when you're testing and playing around, that means something has gone terribly wrong and your invarian are not true. But here, that's why we have it to test our invariance. Okay. Anyway, we have an L, right? So, what does that mean? Well, now so what what it means is that obstacles of P index, right, is less than X is less than uh and keep in mind that all of these are unique, right? So, so it's going to be this, right? So, then now we're splitting up into two pieces of um just this is one piece uh you know, right? And then the other piece is obviously the other one, right?

[00:23:57]Oops.

[00:24:02]Uh and this is the other piece, right?

[00:24:03]And that's it, right? And then what does that mean in terms of in terms of our storage, right? Um well, that means that one, we update this to um we update the obstacle P index, right? And you could maybe do it twice if you like um to update this. Oh, wait. This is not the update, right? uh you only only do this. You update this to zero for now and then update it again.

[00:24:35]Maybe you could do that, right? Like you could update this to because sometimes it's way it's easier and more um you know rest you step it out. Um it's easier to instead of just do one update because there are a lot of different state transitions. Um, you can actually do a removal and then an add as two separate functions and that like not functions like method functions but two different conversations, two different ideas and that allow you to kind of um also add assertions along the way to um to ensure your invariance are correct.

[00:25:09]Right? So we update this. So then now this removes the previous segment.

[00:25:13]Right? And then now we're adding the new segment. Right? So there's one that is at this index right um and it is length of x minus this right and then the the other one is going to be uh you want to update x uh this this distance right and that's it um and again the syntax is a little bit weird this is segmentry stuff so that's why I'm not going too deep into it um but but yeah but and of course if you enough practice and stuff like that, you maybe you could and you know what you're doing, right? Um you may have seen that oh we're doing this and then this obviously this this would just overwrite this anyway. So this is useless, right?

[00:25:59]Um but it is just you know I want to write it out to show you know that's a thing that we could have done right anyway that's basically it um for the update query and then now we can just do the query right so we have um size in query uh and for me it's just you know we have we just break into two cases and it's just getting about the biggest size right because the biggest empty block or block of emptiness or whatever right so then now what are we trying to do Right?

[00:26:28]So we're given X and then now we're trying to find out from X whether you can squeeze in. Right? So okay. So we do the same thing just because we're doing bisect. Right? But then now this gives us the next block, right? Where we're looking for X but everything has to be strictly. So then run P index is equal to index minus one. And then now um right so this is the previous index and remember that obstacles of P in index um you know might is is this thing right but that's one one thing but also obstacles of P index contains length to the next index which is obstacles of index uh or this minus that, right? Um so but so what that means is that uh to get a prefix max what we want is actually P this right. Um yeah.

[00:27:38]Um because now then you get the Wait.

[00:27:46]No, no, no. I mean this is I'm I'm being dumb. I'm being dumb. I'm thinking of something else, another problem or something like that. But now that means that because obstacle P index contains D that means that we actually want to to that's why we have a segment tree, right? is to get the the um the query is it called query? No, it's called max for some reason. Uh to uh from from zero from nothing, right? From all the way to the beginning all the way to opticles of P index minus one, right?

[00:28:23]I spelled this right. Okay. Well, I misspelled P index though because now the the minus one the index before that does not contain well does not contain this index which contains this length right so then now we you know we go maybe max size or whatever max empty block right you go to this right um so that's one piece right and maybe I write like answers right and then here um and there a couple ways You can write this but but but if max empty block is greater than or equal to size then we're already good right um and you can maybe even write you know something like this right and then just return answer but we're not done I just want to um but I always take the opportunities like this to just kind of run it real quick just to see if we kind of have silly you know that's what I mean I I know that this is not compilation error that's not how Python works but but it's just like I I uh as you can see I have a lot of typos uh or you know just confusing things but yeah um of course the uh this doesn't work yet because as we said I mean that's why we're so careful about it is that we're missing the case where um it's like this one actually it is exactly this one where they cut it off right for here we only up return the the left side uh prefix which returns three but we don't return the um you know the the length Okay. So then now we know that we also have a an empty space from obstacles of P index to X. So then we check it right.

[00:30:20]And that should be it. So, I mean, another way to think about it, I guess, if you really wanted to, um, though maybe it falls into issues, um, is that you're adding an you could also add a temporary obstacle and then do a check and then remove it. That would also work, I guess. But, you know, there are nuance there because if there's already an obstacle there, then you have to handle the two obstacle case, which I I don't have to uh, for now. So, yeah. Uh, that looks okay, right? I I don't know if this is correct. Correct. But it's good enough for me to yolo submit. Um yeah. Oh, I forgot about this. But I mean, yeah, you should remove this. But when this is wrong, that means something is wrong anyway. And maybe there's something wrong, right? So, okay, let's see. Right.

[00:31:06]Only 13 cases. Yeah, I mean that there's been something wrong anyway. But um what does that return then?

[00:31:24]Oh, I guess infinities are kind of weird.

[00:31:30]Maybe this assertion is just weird for maybe it doesn't hold for infinities is what I mean because this is just like infinity minus one which maybe is very awkward. Um, but uh is it though? It should still work, right? Cuz basically it's saying that we've put an obstacle at one and then put one at 11, put one at four, put one at eight, and then you have this qu going to 13. Oh, wait. No, I mean, oh wait, no, no, no. This is at the 1 to 11. So that now it's going max of obstacle was to obstacle P index obstacle P index.

[00:32:17]Do I not update this?

[00:32:21]Popsicle P index is. So we up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up up update this to H. So we update um this to zero and then at one which is here we update it to 99999.

[00:32:38]Right?

[00:32:40]So this should have took because the updates one and this returns like probably P index is one, right? So H. So this is actually I mean I'm cur I mean even with the weird infinity thing, it should still work.

[00:33:00]So I don't know why that is unless something's wrong with this of course.

[00:33:05]Um, I guess we'll see.

[00:33:29]Oh, this is definitely wrong. I mean, one of these should be the next index for sure, right? Okay. I mean, yeah, like I said, there a lot of potential for typos. This is what and this assertion kind of helped us a little bit. Otherwise, it would just be um Okay. So, it goes from index. So, that means that we have to set this one.

[00:33:46]Okay. I mean, I don't know what I was looking at, but uh but as you can see, yeah, it's just a easy a relatively easy fix. And I don't know, we could leave this in here or if this is wrong, the code is wrong anyway. So, but we'll just remove it for timing sake. And yolo submit. Uh but yeah, like I said, like the idea I'm okay with possibly silly mistakes a lot of places. Uh and yeah, and that's it. Uh that's kind of funny.

[00:34:10]I mean, I honestly I mean, obviously, it still sucks to get a wrong answer, especially in front of people, but but I'm happy that it kind of turned out because even it proved my point about assertion, right? Um on just a silly typo like this. Um and you know, but yeah. Um I mean, we got it right on the first go. That was pretty good.

[00:34:30]Oh, sorry. Second on one wrong answer, not the first go. Uh, this last time we got two wrong answers. So, that's already better. So, there is a short a much Oh, I was going to say this one is much faster, but then it's just in C++.

[00:34:43]I probably translated. I'm curious what I wrote last time though. I guess I did do segmentry.

[00:34:51]Um, and this is exactly the same. So, maybe maybe the code just got faster or something like this. Um well or like my code I mean this is actually exactly the same. Geez. Uh but um and I even probably had the same typo or something maybe because I have the same print statements here. But everything else actually looks exactly the same. So it's kind of funny. Um yeah. Okay. I mean you know sometimes Larry can be consistent I guess. But uh but yeah but that's it. That's all I have for this one. Um I am curious whether there's like a non segment tree answer. So let's see.

[00:35:32]Okay. Well, maybe not.

[00:35:35]Uh but yeah, let's go over to comprait really quickly. I mean some of this is abstract array with segment. So uh so it is what it is. But for each query the binary search this is on the number of obstacles which is bounded by the number of queries. This is also O of I mean this is O of log q right but this is log n so it's log q plus log n for or m in this case right where m is the the max element right um so log q plus log m per query and then you have q per q query so q time log q plus log m right in pars So, I guess I'll just write it out, right? So, something like that. Um, and that's it.

[00:36:30]That's all I have for this one. Let me know what you think. Thanks for watching. And yeah, I'll show you my segment tree code uh really quickly. Uh, it barely doesn't fit, but hopefully you get the idea. Uh, and then yeah, and you have all this stuff. And that's it. That's all I have for this one. Let me know what you think. Thanks for watching and yeah, stay good. Stay healthy to good mental health. I'll see y'all later and take care. Bye-bye.