Leetcode 3161 | Block Placement Queries | Leetcode POTD | Segment tree + Binary Search | DSA

Ajouté : 2026-06-01

[00:00:00]So, hello and good morning to everyone.

[00:00:01]So, today's lead code question is 3161, which is block placement queries. So, in this question, we are given that we have an infinite number line whose which is starting at zero and extending towards the positive x-axis. Like this is zero, and then we have this number line. And we are given a 2D array named as queries, which contains there are two type of queries. So, first type, that is type one. So, in type one, we have one {comma} x. So, that means that means this is type one query. So, what we need to do is we need to build an obstacle at a distance x from the origin. So, basically, we have to build an obstacle at point at point x, right?

[00:00:48]And they have mentioned that they have guaranteed that there is no obstacle at distance x when the query is asked. That means there was no obstacle already placed at x when this query was asked.

[00:01:01]So, this is type one query where we are given one {comma} x, and we need to build an obstacle at the point number x.

[00:01:08]The type two query is So, in type two query, we are given x and size. So, we have to check we have to check whether it is possible it is possible to place a block it is possible to place a block whose size is sz bef- in the range in the range zero to x, right?

[00:01:28]Such that such that the block entirely lies in this range and and it do- doesn't intersect with any obstacle. So, suppose if you have an obstacle at one, so suppose you have an obstacle at one, and we are given we are given two {comma} let's say x is two x is two and size is three. That is it is possible Is it No, three can't to possible. Let's say it be two. That is it possible to place a block of size two between zero to two?

[00:02:02]Zero to two. It is not possible to place a block of size two between zero to two because we have an obstacle at one. So, that obstacle is intersecting with this.

[00:02:11]So, we have to return false for this.

[00:02:14]Right? So, this is This is type two query. Now, what you need to do is we need to return a boolean array named results where results of I true if we can place the block in the specified I query of type two.

[00:02:30]And if we can't put that block, then we have to return false. Right? So, this is our question statement. So, let's see some examples to get the question more clearly.

[00:02:41]So, if you see So, this is type one query in which we have to put an obstacle at index number two. So, at index number two, we have put an obstacle. Right? Then, this is type two query type two query 2, 3, 3. That means That means we have to place a block place a block whose size is three and from zero to three. That from zero to three, we have to place a block of size three. So, zero size of block three from zero to three. So, this will be our block. But, if you see, there is an obstacle at at index number two. So, this block can't be placed. So, that's why we have put false over here. Then, next is 2, 3, 1.

[00:03:31]So, now the size of our block now is one. And we have to put from zero to in between zero to three. In between zero to three, we have to place a block of size one. Size one. So, we can put a block of size two here. So, even we can put a block of size one. So, for this, we have to we return true because we can put our block over here, right? Or over here.

[00:03:57]Or between two to three also we can put our block, right? So, there are three places where we can put this block. Then next we see 2 {comma} 2 {comma} 2. That is we have to put a block of size two from zero to two.

[00:04:16]So, yes. From zero to two we have a gap.

[00:04:19]We have a gap of size two. So, we can put we can put this block over here. So, we have written true for this also.

[00:04:28]So, this is our example.

[00:04:30]So, let's see the next example. So, in the next example first we have put to a an obstacle at point number seven. At point number seven we have put an obstacle. Then the next query is 2 {comma} 7 {comma} 6. That is size is six and x is equal to seven. That is we have to put a block of size six in between zero to seven. So, in between zero to seven our gap is in between zero to seven our gap is gap is equal to seven.

[00:05:03]So, we have a gap of seven. So, we can put a block of size six in between that gap. So, we return true for this one.

[00:05:12]Then the next is next is 2 {comma} 7 {comma} 5. So, here size is five and again like uh x is equal to seven. So, we again can put this block in a gap of seven. Right?

[00:05:27]Oh, sorry. Before that before that we have a type one query. So, we have to put an obstacle at point number two. At point number two, right?

[00:05:39]So, we have put an obstacle at point number two. Now, from zero to two we have a gap of two and then from two to seven we have gap of five. Now we have two {comma} seven {comma} five. We have two {comma} seven {comma} five. So size is five.

[00:05:54]And we have to put from zero to seven.

[00:05:57]So we have to check whether we have a gap of five. We have a gap of five or more between zero to seven. Yes, between zero to seven we have a gap of five. So we can put this block. So we return true.

[00:06:10]Then the last one. Last one is two {comma} seven {comma} six. So now our size is equal to six. So we need we need a gap of six. We need a gap of six between any two obstacles to put this block between the range zero to seven.

[00:06:26]So if we see between the range zero to seven maximum gap maximum gap is of size five which is lesser than six. So we can't put this block. Right? We can't put this block. So we put return false for this.

[00:06:42]So this is example number two.

[00:06:45]So let's see the constraints.

[00:06:47]So the total number of queries the total number of queries is 15 into 10 key power four. And the queries of I dot length can be from two to three. Two to three. If type one query then the length will be two. If type two query then the length will be three.

[00:07:05]And queries of I and at index zero we have either one or two. That is type. Either type one or type two. And X and size can be five into 10 key power four. Minimum five into 10 key power four or maximum three into queries dot length. So three into queries dot length will be 15 into 10 key power four at max. But in that case it will be five into 10 key power four. So at max at max the X and size X and size can be five into 10 key power four. Right? We'll be using this constraint to solve our problem, right?

[00:07:46]And it is given that the input is generated such that for queries of type one, no obstacle exists at distance x when the query is asked. So, all the obstacles are unique. There are no duplicate obstacles, right? That is for any point any point, there are unique obstacles. And also, the input are generated such that there is at least one query of type two. At least one query of type two will be there in the question. So, these are the constraints.

[00:08:13]So, let's start with the approach part.

[00:08:15]So, we have this type two query. So, in type two query, what we need to do? We need to check whether can we put a block whose size is sz in the range 0 to x 0 to x. So, basically, that means that means we need we need a continuous gap.

[00:08:36]We need a continuous obstacle-free segment, or we can say we need a gap we need a continuous gap whose at least size should be sz so that we can put a block we can put a block of size sz in the range 0 to x, right? So, for that is type this is type two query.

[00:08:57]That means that means in the range in the range 0 to x 0 to x, we need we need a continuous gap between the obstacle, a continuous gap between the obstacle such that their gap should have at least sz as the minimum length so that we can put this block, right?

[00:09:17]So, now, instead of thinking about putting the blocks, what we'll think?

[00:09:22]We'll think about the gaps between the obstacles. We'll think about the gaps between the obstacles, right?

[00:09:29]So, let's see an example. Suppose our obstacles are located obstacles are located at at 0 2 seven, 10. Then, if you see between zero to two, we have a gap of two. Between two to seven, we have a gap of five. And between seven to 10, we have a gap of three. So, so these are the free segments or we can say these are the gaps. These are the gaps between the obstacles. Right?

[00:10:01]So, when we get a block, when we get a block, that block that block should fit should fit inside these gaps inside these gaps. Right?

[00:10:12]So, for a type two query, for a type two query, we only need to know we only need to know that what is the largest free segment that we have inside the range zero to X. Right? We need the largest free segment or we need to know about the largest gap that we have that we have in the range zero to X. Right? If if the largest gap if the largest gap is greater than or equal to SZ, is greater than or equal to the size of the block, then then our answer will be true. Then we can fit that block in that particular gap. If the largest block size is less than SZ, less than size, then we can't fit the block, so we return false.

[00:11:00]Right?

[00:11:02]So, we have to return false.

[00:11:11]understood type two queries. So, the next thing that we need to understand is that instead of processing the queries in the given order, that is forward order, what we'll do is we'll process the queries in the backward order.

[00:11:24]Right? In the backward order. Right?

[00:11:27]So, what happens if you process the why we do not forward the process the queries in the forward order? So, suppose we have we have the what you call obstacles at zero and 10. So, when we insert, let's say some obstacle at X point, some obstacle at X point, then then earlier our gap was of 10. Now, we need to divide the gap in X and 10 minus X two parts. Right? We need to divide the gap into two parts, right? And maintaining such smaller gaps or maintaining such splits maintaining such splits is difficult for us, right? Is difficult for us, right? Inserting Inserting that is inserting a new inserting a new obstacle inserting a new obstacle is difficult for us. So, what we do is So, what we do is we reverse we reverse the queries.

[00:12:29]Like we process the queries from end end to beginning end to beginning. So, if from front direction, if you have to insert, then from back direction, we need to remove. We need to remove an obstacle.

[00:12:46]So, what we do is initially initially we insert all the obstacles that appears to us that appears to us, right? We put all the obstacles on the number line, right?

[00:12:58]And then start pro processing from the last. Then start processing from the last. So, in reverse for type one queries, basically we have to for type one queries, we need to insert the obstacles. But But as we already inserted all the obstacles, so when we come back, so when we come back from the last, so when we get a type one query, type one query, that obstacle we have already inserted while while going forward. So, when we process the queries from the last, then when we get a type one query, then we need we need to remove the obstacle. We need to remove the obstacle, right?

[00:13:37]So, basically removing the obstacle means we have let's say two gaps, right?

[00:13:42]Suppose we have zero, we have 10, and we have an obstacle at X. We have this gap X and this gap 10 minus X. So, when we remove this obstacle X, now we need to merge these two gaps. We need to merge these two gaps. So, merging these gaps merging these gaps is easier for us easier for us comparatively to splitting compared to splitting the splitting the gap. So, that's why that's why we are processing we are processing the queries in the reverse direction, right? I hope you get this point, right?

[00:14:17]So, it is here an example is given.

[00:14:19]Suppose we have zero to seven, and when we remove two, we have to merge this gap zero to seven. So, these two gaps two and five is merged into a gap of seven.

[00:14:29]It's like uh this that's is easy to maintain, and that's why we are processing in the reverse direction, right? So, the next thing the next thing that we need to understand is So, suppose we have an obstacle at some position P. So, what we need to do is we need to store what is a gap that we have at this position P, right? That is position minus the index of the the position of the previous obstacle. So, this gap this is the gap at this position of the obstacle. Now, if we have if you have obstacle at zero two seven 10. So, at two at two, what will be the gap? So, gap of two will be its current position, that is two, minus the previous obstacle, that is zero. So, two minus zero is two.

[00:15:21]Then gap of seven gap of seven will be its current position seven minus previous obstacle is at two. So, gap of two is seven minus two, five. Similarly, we find gap of 10, that is 10 minus seven, that is three, right? So, we find these gaps, right? We find these gaps between the obstacle, right? So, at So, we have we have positions and we have the gap that is ending at that particular position. So, at position two, we have a gap of two. At position seven, we have a gap of five. At position 10, we have a gap of three. And now, what we'll do is we store we store these gaps we store these gaps in the in the segment tree in the segment tree, right?

[00:16:10]And and when we need to process a type two query, when we need to process a type two query, so basically, what we need? We need to find the maximum gap.

[00:16:20]We need to find the maximum gap in the range zero to X. So, basically, range so range updates or range queries, so that's why we'll be using segment tree here, right? So, we can easily find the maximum gap maximum gap from the segment tree, right? In the range zero to X. So, that's why we are storing the gap values, right? And if the maximum gap if the maximum gap is greater than equal to size, then our answer will be true, right?

[00:16:54]So, let's see what does the segment tree query will do and how it will happen. So, we have seen at gap of two, we have gap two. At seven, we have gap of five. At 10, we have gap of three.

[00:17:08]And now, suppose we have a query we have a query zero comma seven from zero comma seven. So, if we see if we see what is the maximum gap from 0 to 7 in the range 0 to 7. So, if we see in the range 0 to 7 the maximum gap is 5. So, when we query the segment tree a range that is 0 to x, it will give us the maximum gap. It will give us the maximum gap in that range. So, in the range 0 to 7 the maximum gap is 5.

[00:17:41]So, we get 5 as the answer. So, we get 5 as the answer.

[00:17:45]Right? That is the maximum gap maximum gap which is which is before x which is before x, right?

[00:17:56]So, this is we get from the This is what we get from the segment tree query. Now, we'll understand how we'll process a type two query. What we'll do when we get a type two query? So, we have considered three obstacles. We have considered three obstacles at 0, 2, and 7. Right? At 0, 2, and 7. So, here gap is 2. Here gap is 5. And now what we need to do is we need to query 2 6 uh query of type two whose size is four size is four and x is equal to six. That is we have to find we have to find a gap we have to find a gap of size greater than equal to four in the range 0 to 6 in the range 0 to 6 such for fitting this block for fitting this block, right? This is the gap that we need. So, what we do is So, we have x we have x x is equal to six. So, first what we need to do is we need to find the previous obstacle which is lesser than or equal to x last obstacle which is lesser than or equal to x. So, here we have 0 to 7. So, last obstacle which is lesser than or equal to x will be two. So, we get our previous obstacle as two, right?

[00:19:11]So, the next thing the next thing that we need to do is in step two, we need to find a largest gap, a largest gap from the range zero to last obstacle, zero to last obstacle. So, here here in zero to to the maximum gap that we have is two. So, this query this query will give us the answer as two, right?

[00:19:36]This will give us the answer as two.

[00:19:38]Now, if you have seen if you have seen we have zero two and seven and we have asked that six from zero to six and we have find the maximum gap from zero to two. So, here the maximum gap is two.

[00:19:54]But, if you have seen there is some part still left within two to six that we haven't considered and that part's uh gap is four. So, this gap is four.

[00:20:04]So, we take So, this is our this is our tail interval.

[00:20:08]This is called as this is our tail interval, right? So, we have to consider that tail interval also, right? So, tail interval is distance between x minus x minus position of previous obstacle, position of previous obstacle, right?

[00:20:26]So, that distance is tail interval. So, we have considered that tail interval also. So, tail interval distance is four. Now, what we do is we considered the maximum gap, maximum gap of So, from the query from the query we get the answer is best. Let's say the answer is best and this is tail. So, we take maximum of query that is from zero to previous obstacle, zero to previous obstacle, {comma} tail is four and this is two. So, maximum of two {comma} four is four. So, the maximum gap that we get from zero to six is four and our block size block size was also four.

[00:21:09]So that block can fit in, right?

[00:21:12]So we find the we find the maximum block size or maximum gap from here. Then once we find the maximum uh what we call gap, then we check whether it is feasible to fit the block.

[00:21:24]It is feasible to fit the block. So we check if best is greater than or equal to size, that is four is greater than or equal to four, then our answer is true.

[00:21:34]So if you see what are the four steps.

[00:21:37]First step, we find a we find a previous obstacle. We find a previous obstacle.

[00:21:43]Second step, we find a maximum gap.

[00:21:47]Maximum gap in between zero to previous obstacle using the segment tree. Then the third thing, that is tail interval.

[00:21:55]Tail interval is x minus x minus previous obstacle. And then and then we find maximum of maximum of step two {comma} step three.

[00:22:07]The answer that we get from here and the tail interval. And that is let's say that is our gap.

[00:22:13]And the fourth step is feasibility check. So if our gap is greater than or equal to size, then we return true.

[00:22:20]Return true, else we return false for that particular type two query. So these are our four steps for type two query.

[00:22:29]These are our four steps for type two query.

[00:22:32]Now next thing we will see is how we'll process type one queries.

[00:22:39]So in type one query, we have one {comma} x. That means That means we have to insert an obstacle at point x. But here here we are processing in the backward direction. So instead of inserting, we will remove obstacle at x.

[00:22:54]So suppose we have our current obstacles at point zero {comma} two {comma} seven.

[00:23:00]zero two seven. So it gaps will be 2 and 5. Now, we have to remove 2. Now, we have to remove 2. So, what will be the steps? So, first of all, first step is we'll find the neighbors. We'll find the neighbors of the obstacle obstacle that we have to remove. So, our obstacle x is equal to 2. So, left neighbor left position left position is 0 and right position is right position is 7. That is let's say 0 2 7. So, first we'll find the neighbors of the obstacle that we remove. So, 0 and 7 are the neighbors. Right, this is step one. Then, the step two. So, we have gap of 2 is equal to 2. If you see, if you see 0 2 7. So, gap of 2 is equal to 2. Now, 2 has been removed. So, we we need to make gap of 2 is equal to 0. So, we have to update 2 to 0. That is gap at 2 will be 0 because we removed the obstacle 2. So, this is a second step that we make the gap of the removed obstacle x as 0. So, we update that. Now, the third thing third thing so, we have removed 0. We have removed sorry, 2. Now, we need to merge we need to merge this gap. So, earlier gap of 7 gap of 7 was 5. That is 7 minus 2 5.

[00:24:25]But, now 2 has been removed. So, we need to update gap of 7 as as 7 minus 0 as 7.

[00:24:32]Right, so we now next step is we merge the gap. So, we update we update the next step. That is 7 with the distance as 7 minus left. That is 0.

[00:24:47]Right minus left as So, right neighbor minus left neighbor will be the new gap will be the new gap. So, in the step three, we have we have merged the merged the gap in the segment tree.

[00:25:02]And the in fourth step, we remove the obstacle from our set. We remove the obstacle from our set. So, earlier in the obstacles we have zero to seven. So, we remove this from the set. So, we'll be left with zero and seven as the obstacles. So, what with the what are the four steps? So, first step First step, we make gap of Sorry, in the first step we find the neighbors. That is left position and right position. Right position of the uh obstacle that we are removing. In the second step, we make gap of x is equal to zero. In third step, we merge the we merge the gaps. We merge the gaps.

[00:25:44]That is gap of right. We update gap of right position to right minus left to right minus left. And in the fourth step, we remove the obstacle from the set. So, these are the four steps for removing or for processing type one query or processing type one query.

[00:26:02]So, let's see a dry run.

[00:26:05]So, here we have queries 1 2 1 7 2 6 4.

[00:26:09]So, first of all, what we'll do is we'll insert all the obstacles. So, here we have obstacle at two, obstacle at seven, and we are considering an obstacle at zero. So, we have obstacle at zero, two, and seven. Right? So, now using these obstacles So, here if you see what is the gap here? Gap here is five. Gap here is Sorry, here is two, here is five.

[00:26:30]That is gap of two is equal to two, and gap of seven is equal to five. Now, I'll show you I'll show you how we'll build the segment tree from this thing. Right? How we'll build the segment tree from this.

[00:26:46]So, what we have done is we have taken the first node. First node will store from zero to It is five into 10 to the power 4. 5 into 10 to the power 4. So we divide it into two parts. So this node will store zero to 5 into 10 to the power 4 is So it will store this.

[00:27:04]Then this node will be stored from 25,000 to 5 into 10 to the power 4. Like it will store the maximum gap in this range. Then we again divide this range. Right?

[00:27:15]So at at node two, that is at node two, that is range is two comma two, we have gap of two. So we have stored this gap here.

[00:27:26]Right?

[00:27:27]And then suppose it has a it has a some parent. So that parent will take the maximum gap from this node and maximum gap from this right node and store the maximum store the maximum gap at this node and return the maximum gap to its parent. So this way this way all the nodes all the nodes all the nodes will be stored will be stored maximum gap in that in their range. Right? So this way we'll build the segment tree using the gaps. So similarly for seven, suppose we have seven here. So at node seven comma seven, it will store maximum gap five and return that gap to its parent. So now suppose two and five two and five have this common parent here.

[00:28:13]Let's assume. So two will return the maximum gap two and here seven will return the maximum gap five. So it will store it will store the maximum gap of two comma five. It will store maximum gap five and return that maximum gap to its parent. So in this way in this way we'll build all the we'll build the segment tree. We'll build the segment tree.

[00:28:34]Right? So we have built the segment tree. And when we query when we query the segment tree like this is query two six comma four. So here our size is four. So we find the maximum gap in the range. This is X. In the range 0 to X.

[00:28:49]In the range 0 to X, we find the we find the maximum gap.

[00:28:54]Right? Using the using doing query over the segment tree. So, here if you see what is the largest obstacle that we get? We get two.

[00:29:07]In the from the segment tree, we get two as the answer. Then so largest complete gap is two. And the tail part tail part is which is 6 - 2, that is four. So, if you see we have 0 to and 7. And we are querying for up to this part 0 to 6, right?

[00:29:26]So, we query over 0 to 2. So, we find the maximum gap over 0 to 2, which will return us two. So, we have ignored this part. So, this part gap is four. So, we take maximum of these two. So, 2 {comma} 4, maximum of 2 {comma} 4 is four. So, best answer is four. And even our block size is four. So, four is greater than or equal to four, so answer is true for this query. Right? So, this way we have processed the last query. Now, we get a type one query. We get a type one query.

[00:29:55]So, we need to remove this obstacle. We need to remove this obstacle as we are processing in the backward direction. So, here we have 0 to 7. So, we are removing seven. So, first we'll find the neighbors. So, left neighbor is two. Right neighbor, there is no right neighbor for seven. Right?

[00:30:13]And the next step is we'll make gap of seven as zero. We make gap of seven as zero.

[00:30:20]So, now we'll I'll show you how we'll update this gap of seven. So, in the segment tree wait, I'll draw the segment tree and then I'll show you.

[00:30:28]So, in the segment tree, we have 0 to 5 into 10 to the power 4. Then I have this it is divided into two parts. So, suppose here we have 7 {comma} 7. Left and right is 7 {comma} 7. So, at 7 {comma} 7 we have gap of five. So, we find this node. We find we go to this node and we find So, we make this gap as zero. Then we go to its parent. Then we go to its parent. So, its parents will take max maximum gap from its left child and maximum gap from its right child. So, from right child it will get zero and let's say from left child it will get X.

[00:31:03]So, it will update its gap its maximum gap and return that value to its parent and then its parent will update that value and will return to its parent. So, so in this way in this way all the nodes all the nodes that are affected that are affected will be updated will be updated with the new value will be updated with the new value. So, gap of seven will gap of seven has become zero, right?

[00:31:32]So, this is a rightmost node. This is a rightmost node. That's why there is no need there is no need to merge. There is no need to merge. But, suppose if you have removed two, if you have removed two, that is if you have removed two instead of seven, then we need to merge this gap. Then we need to First, we have to make gap of two as zero. Gap of two as zero and then in the next step we have to make gap of seven as right seven minus left.

[00:32:02]That is seven. So, we need to update this also. So, if if the removed if the removed node is a is in middle or it has left and right, then we need to do two updates. But, if it is a boundary points if it is a boundary points obstacle, then we have to do only one update, right? So, in this way in this way we'll process the all the queries. So, let's move to the code part. So, in the code part we have taken a vector in segment to store the segment tree and we have taken them max value because we are given X and size max value can be 5 into 10 to power 4. So, we have taken that value. And then this is our main function, that is update function. So, it has a node. It has left and right, that is the that is the range range of the node, range of node. Then index index is basically the index that we have to update. And value is the value with by which we have to update the index. So, let's first we'll find if we get the original node, that is left and right range is equal to is equal, then we update the value of the node in the segment tree by the new value and we return. But if you do not get the actual node, then we find Suppose we have 0 to 5 into 10 to power 4. So, we find on which side on which side we have this node. Either on left side either on left side or on the right side. So, which side has this node? So, suppose this side has no this node, then we go to this side and then again check until we do not get the exact node. So, once we get the exact node, then we update the value.

[00:33:46]And then at the end we update the parent, that is the parent will take maximum value from its left child and right child and then store the updated value to it. And then So, suppose here 7 is there, then 7 will return that value that suppose this is a parent of 7. So, it will take value from left child and right child and then update its its maximum gap. And then its parent will take value from it. And then it that parent will also update that value. So, this is a update function.

[00:34:20]So, next function is query function. So, query function helps us to find the help us to find the maximum gap in a query range. So, this is our query range.

[00:34:30]And this left and right is the range of the node.

[00:34:34]So, first thing, if if the node range if the node is totally out if there is no overlapping if there is no overlapping between the between the query range and the node range, then we return zero. Then we return zero.

[00:34:52]The second case is there is full overlap. There is full overlap. That is the whole node whole node is is inside the query range. Then we return the value or then we return the maximum gap stored at that node. Then the third case, partial overlapping. That is the node value or node range is partially overlapping with the query range or the query range is partially overlapping with the node range, then then we query both of its child, left child and right child, right? So, this is the query function. It has three things.

[00:35:24]No overlap case, no overlap case. In that case, we return zero. Second case, full overlap. In full overlap, we directly return the value. And partial overlap, in that case, we check the child's. We find the value inside the child's. So, this is our query function.

[00:35:42]Then we come to our main function. So, in main function, we have we have first declared the size for the segment tree which is 4 into max plus one because that is the total number of nodes that we have in the segment tree. Then we have a set to store all the obstacles.

[00:35:58]And we have inserted zero as the obstacle. And then we have iterated all over all the queries. And if there is type one query, that means we have to insert an obstacle. So, we have stored all the obstacles in the in the obstacle set because we have to reach to the final state. Where in final state, we should have all the obstacles.

[00:36:21]And then after reaching the final state, we will process in the backward direction, right? And then we have stored all the positions where we have the obstacles present. We have stored all the positions where we have we have the obstacles present. And then then what we'll do is then we store the gaps.

[00:36:38]Then we store the gaps in the segment tree. Right? So, for that we have the we have called our node one, node one, whose range is zero to max. Zero to max.

[00:36:50]And and the index value is position of I. And the gap value is position of my I minus position of I minus one. That is the gap value that we have to store at that particular index. Right? So, this will build this will build our segment tree for us. Then what we'll do is then we iterate over the queries over the queries from last to first. So, if you get a type two query, if you get a type two query, then we have a X and we have a size.

[00:37:22]Right? So, we have to find we have to First we need to First we find a previous obstacle we previous obstacle whose position is less than X, whose position is less than or equal to X. Right? Less than or equal to X. So, that we can fit the block. So, first we find the previous value.

[00:37:41]Previous First we find the previous obstacle. So, in previous obstacle we find the index value or position of that. Right? And then we query then we query the maximum value or maximum gap from zero to that previous obstacle, zero to that previous obstacle. So, that answer that maximum gap we have stored in the variable named as best. And then I have already explained this is the tail part. Tail part.

[00:38:09]So, let me again explain you. Suppose we have zero to seven.

[00:38:13]We have three obstacles zero, two, and seven.

[00:38:16]And we are finding for X is equal to six and for X is equal to six. So, we have queried we have queried for zero to two. We have queried the maximum gap for for zero to two, but this part two to six two to six is the tail part. That is x minus previous obstacle. That part is still left. So, it may be possible that we have a maximum gap created here. So, we consider that maximum gap also. So, that's why we're taking maximum of best.

[00:38:42]Best is the query part and x minus previous obstacle is the this part. That is that is tail part and then we have taken the best of these two and then we compare if best is greater than or equal to size, then our answer is true, else our answer is false. So, this is this is the way we process type two queries.

[00:39:02]Now, we'll see how we'll process type one queries.

[00:39:05]So, in type one queries, we have to remove the obstacle present at point x.

[00:39:11]Obstacle present at point x. So, first we find the position of First, we find the position of that obstacle in our obstacle vector and then we find the neighbors of it. We find the neighbors of it. That is left position, right? And we find the right of it, right? And before that before that we what we do, we make gap of x. We update gap of x is equal to zero. We update gap of x is equal to zero and then we check the right of it. So, if if the right of it is not equal to obstacle {dot} end, that means our current obstacle is present in between in between. So, we have to merge the gaps. So, we have to merge the gaps.

[00:39:56]Suppose we have zero, again, two and seven and we have to remove two.

[00:40:02]We have to remove two. So, we need to merge the gap between zero and seven.

[00:40:06]So, this part this part is to merge the gaps. This part is to merge the gap. So, we are updating the right position. That is we are updating the right position with the new gap. That is right position minus left position. So earlier gap of seven is equal to seven minus two five, but now gap of seven will be seven minus zero. So seven is the right of two and zero is the left of two. So that's why you see we are updating the gap. And then at the end we erase the obstacle from the obstacle vector and then at the end. So here we are storing the answer in the reverse direction. So we need to reverse the answer and we return our answer. So this is the whole explanation. So I hope you get the solution. So if you like the solution, please make sure to like, share, and subscribe the channel. Thank you.