Using C++ STL to simplify hard problems

Indiziert: 2026-05-17

[00:00:00]In this video, we will look at four problems in increasing order of difficulty and we will also look at how to optimize these problems using standard data structures that are present in C++ STL. And the optimizations that we would do is to start from O of N cq solution then optimize it to O of N² then to O of N login and finally there is also an O of N solution to this problem which we will discuss towards the end of this video.

[00:00:35]So if you want to know whether this video is relevant to you or not, I'll quickly describe all the four problem statements that we are going to discuss.

[00:00:45]So you have a 2D grid and you know that there is no orientation of the 2D grid because this is infinite.

[00:00:56]So in the first version of this problem, you have to partition this 2D grid by placing a vertical barrier.

[00:01:07]So this white line that you see over here, this white vertical line that you see over here, this is a barrier which does not cross any of the existing points. So all these points that you see, they are points with integer coordinates x y and you have to place a vertical barrier. And vertical barrier is nothing but a straight line that uh that has where x is fixed and your y varies.

[00:01:42]Now you can see that after placing a barrier the region has been divided into two parts. One is the left part and one is the right part. So this is the left part that you see over here and this is the right part of the region that you see over here. And since you were given n different points on the 2D grid after placing these barriers you can see that all the points that land on the left half I have colored them on as red and all the points that land on the right half I have colored them in green.

[00:02:19]So you have to find out how many ways in how many ways can you place vertical barriers such that the region gets uniquely divided into two halves. And what do we mean by uniquely divided into two regions? It's that in this barrier placement in this placement you can see that these three points are on the left region. But if you chose another barrier placement like so, if you had this barrier placement, then you can see that in this barrier placement only these two elements are in the left region and all the remaining elements are in the right region. So that is why the color the concept of color is introduced to ensure that uh two configurations of barriers are different. If the color of at least one of the points after the barrier placement is different.

[00:03:20]And now you can also see that if you place another barrier over here, you just have to place a single barrier.

[00:03:28]By the way, you don't have to place multiple barriers. You have to place a single barrier, but you have to do it one by one. So if you can see that if instead of this barrier you had this barrier then this is a not this is not a different configuration because the points in the left half they are still the same.

[00:03:48]So now you can clearly see that the if you have so if this is one point and this is another point and of course they are on integer coordinates then in this entire region you can only place one barrier because even if you placed multiple multiple barriers like so they won't really be helpful because all of them will produce the same left half and the same right half.

[00:04:16]So in the first version of the problem you have to find out in how many ways can you place the barriers such that the region is nicely split into left and the right parts and in the second version of the problem you have to answer the same query but this time you have you have to place a horizontal barrier instead of a vertical one. So for example, if you place this vertical barrier, this horizontal barrier over here, then everything that is below this barrier, all the points that are below, they will be colored in let's say yellow and all the points that are above this barrier this one they will be colored in blue.

[00:04:56]So you have to find out in how many ways can you place barriers such that the region is split into up and down parts.

[00:05:03]And then in the third variation we want to find out the number of ways to place two barriers. Right now we are placing barriers one at a time but this time we want to place two barriers and the region would some look something like this. You can visualize that if this is the first barrier that you place and if this is the second barrier that you place. Of course one barrier is horizontal, one barrier is vertical.

[00:05:26]Then you can see that the region is split into four quadrants. So some points will be in this quadrant, some in this quadrant, some in this quadrant and some points in this quadrant. So you have to figure out in how many ways can you place two barriers, two vertical lines so that the all so that at least one at least one point is not the same in one of the quadrants if you are comparing for whether two barrier placements are equal or not. And in the final version we will discuss that in how many ways can you create these four quadrants such that each of these four quadrants has at least one point from the input that is given to you.

[00:06:10]That is you cannot have some points here, some points here, some points here and in this last quadrant a point is missing. So if there is no point in the last quadrant then this barrier placement will not be considered as legal.

[00:06:28]So let's discuss the first version first uh which is how do you place barriers such that the left half and the right half are how do you place barrier such that the region is divided into the left half and right half. So this part is actually easy to see if you think about it. You know that the barrier could be where could the barrier be? It could either be to the left of this element.

[00:07:00]So it could you could place a barrier over here.

[00:07:06]When you do you can see that all the points in this region they will be colored in green and no point will be colored in red. So left half is empty and all the points are in the right region. So that is a valid barrier placement.

[00:07:24]Then what is the second possible choice or let me actually keep it?

[00:07:31]You could place the barrier over here.

[00:07:39]But if you place the third barrier over here, if you place another barrier over here, the this and this are identical because the set of points does not change. So let's remove this. Then since this point and this point they lie on the same vertical line and actually barrier should not touch any point. So that doesn't matter. So you can see that you can place one barrier over here.

[00:08:01]Then you can place another barrier here and then another barrier over here. One barrier goes One barrier over here, one over here, one over here.

[00:08:19]And then one last barrier over here. And in this last barrier, you can see that all the points are on the left side and the right region is empty.

[00:08:32]Then looking at this, what can you conclude? You can see that there is no other way to pos to place the barriers.

[00:08:39]So you can notice that the total number of barriers is equal to what? Is it equal to the total number of points that you have? Not really because some points could lie on the same same vertical line. So that's why they don't actually create the gaps for barriers to exist. So for example this point and this point had enough gap between them such that you could embed a barrier vertical barrier in between them. So therefore you can see that if you had if you find out the number of unique number of points with with different x value. So for these two points the x value is different only the y value is different. So this is one X.

[00:09:31]Then this is the second. This is the third X. Fourth point with a different X. Fifth point with a different X. Sixth point. And then seventh point with a different X and eighth point with a different X. So there are total of eight points. So there are a total of eight unique values. And how many barriers are there? You can say that it is 1 2 3 4 5 6 7 8 9. So there are a total of nine barriers and this actually feels intuitive as well if you think about it. So if you have like let's say one point is here another point is here but then there is another point vertically downwards below it then you can only place a barrier either in between these two elements or to the left hand side or to the right hand side. So since you have like let's say if there were three elements three unique X so this is one point second point and third point. So you can place the barrier 1 2 3 or four.

[00:10:36]So that's why the answer is simply the count of unique x.

[00:10:42]You can say that the answer is the count of unique x coordinate + 1. This is the answer for the first problem where you were asked to partition the entire set into the left and the right region. Now how do you solve for the up and up and down region? So for the up and down region you can follow a similar strategy you can see for the up and down region this time you have to place horizontal barriers. So if you want to place horizontal barriers, you can you can decide to place a barrier over here.

[00:11:27]You can decide to place this barrier or you can decide to place this bar place this barrier or this barrier or this barrier or this and so on. But either way you can see that the answer would still remain the same. The answer would be unique x unique unique y values + 1.

[00:11:58]Now what about the case where you want to place the barriers but you want to you want to add both the you want to add both both kinds of barriers.

[00:12:14]So in this example you can see that one possible way is to add a barrier over here and then add a barrier over here.

[00:12:29]This is one configuration. But how do you find out all the configuration? So for finding out all the configuration you can realize that you can start incremental fashion. You can start in an incremental fashion. So once you have placed this vertical barrier over here then the region is already split into the left half and the right half then all you have to do is start placing vertical barriers sorry horizontal barriers. So you can do that by going over each unique values and every time you find a unique value. If you draw a big horizontal line, you can see that you are already getting four quadrants.

[00:13:11]So you could draw a horizontal line over here or you can draw a horizontal line starting from here. So if you do draw this horizontal line, so this is the first quadrant, second quadrant, this entire thing is the third quadrant and this entire thing is the fourth quadrant. Or you can draw a horizontal line after this element or after this element or after this elements and so on. So you can see that for each for each vertical line the choice of the horizontal line does not change. You still have that many choices. So the answer for the third version would be simply would simply be product of all of these. So unique x unique x + 1 into unique y.

[00:14:01]Now let's talk about the last and the hard version of this problem where you want to place the horizontal and vertical barrier. But you also have to ensure that each quadrant that you are creating that should contain at least one point. Now why will this current strategy of unique x + 1 into unique y + 1 not work? Let's look at a counter example on why it will not work. So suppose this is the vertical barrier that you have placed.

[00:14:35]Let's say that uh this is the ver this is the vertical barrier that you have placed. Now if you let's assume that you had one point over here this is one of the points and then this is one of the points.

[00:14:56]Then in the previous case when when we when we were discussing how to place horizontal barriers, we said that you could place one horizontal barrier like so and then you could also place another horizontal barrier like so and then another horizontal barrier like so. But you can see that in this scenario only one barrier is valid which is the one it is this one.

[00:15:26]this barrier that you see over here.

[00:15:29]Why is that true? Because for this barrier, you can see that this first quadrant has no point.

[00:15:40]Second quadrant has no point. Third quadrant has a point and fourth quadrant also has a point. But the problem says that you have to ensure that all the quadrants have a point. So how do you determine if this barrier placement is legal or not? So determining that is easy. You just create all the four quadrants first, second, third and fourth and you check if there is at least one point in each of them because the total number of possibilities is this without any restrictions on the num number of points that can be on in the quadrant. So of course if you explore all the possibilities this is kind of the brute force and you eliminate the possibilities which is not according to the problem statement then you would have found your answer. So how do we do that? We we will do we will simply try to simulate this strategy by placing vertical barriers.

[00:16:45]And once we have placed vertical barriers, when we are at this vertical barrier, we will also try to place all the horizontal barriers and see which one of them are legal and if they are legal, we'll increase their count. So let's look at the code for that uh idea. So first you iterate over all the possible barriers that is the barriers can only be placed after immediately after the integer point that you have. Here you can see that if this is three, if the x value of this coordinate is three, I can place a barrier just after it because four will be over here because we know that all the points are integers and barriers they do not touch any of the elements. So we iterate over all the possible vertical barrier and for that we try to try try all the horizontal barriers and the horizontal barriers can simply be after all the unique y's that exist in the array. So we iterate over all the unique y and then so if this is your hor if this is your vertical barrier that you have placed and you want to test whether this vertical barrier that you just placed which was immediately after the element whose coordinate is y then you have to find out is there any is there at least one element in each of these four quadrants and how do you do that? So you know that first how do you decide if the point will be in the left region or on the right region. So since you have already decided to use the barrier as XB then any point whose x coordinate is less than or equal to xb that will be in the left half. So that's why you see that you iterate over all the points and if the left coordinate if the x value is less than or equal to the barrier because why am I adding equal to because if the barrier is three so if the element left to the barrier has x coordinate 3 you can assume that we just placed the barrier as 3.5 because you don't have to touch the integer value.

[00:19:06]So if the x value of the element is less than the barrier then you know that the element right li lies in the left region. Now whether or not it lies in the top part or the bottom part that is yet to be seen but since you have also decided to place this vertical barrier you see whether this element.

[00:19:30]So if the point is on the left half then you just check whether that point is below the horizontal barrier that you have just placed or after it. So if the y value of that point is smaller than this y barrier that you have placed then that point will be in this quadrant. So or if the value is bigger then it will be in the top left section or in the bottom left section. Same thing you repeat for the right hand side. So in this manner you can figure out that once you have placed this hor vertical and the horizontal barriers you can figure out is there at least one point here here and here. So the time complexity you can see it is O of N cube. Why is it O of N cube? because you are iterating over all the possible vertical barriers that you place and then iterating over all the horizontal barriers that you place and then you are iterating over all the points to see in which quadrants does it lie. So now let's try to optimize this. But before doing the optimization we will rewrite this solution in such a way that it can be optimized because right now we are just simulating the strategy. Can we still do NQ but with something better?

[00:20:46]So let's see what let's see how to determine if the point is on the left hand side or on the right hand side.

[00:20:56]So assume that you have placed this barrier.

[00:20:59]This is the vertical barrier that you have placed and this is the horizontal barrier that you have placed.

[00:21:06]Now consider any point and you want to know whether it is in the left whether it is in this quadrant, this quadrant, this quadrant or this quadrant.

[00:21:20]How do you do that? And how do you ensure that this barrier is at least valid like it contains some points in some quadrants. Now let's look at the assume that you have not yet placed the this barrier like uh let's get rid of this.

[00:21:44]So actually let's start by first placing the vertical barrier and let's look at what are the cases in which the horizontal barrier that you would place would result in some points being missed from the quadrants. Let's focus on the first quadrant and we want to know uh when would you miss some points in the first quadrant. So assume that the points are distributed like so. One point is here, one point is here, one point is here, one point is here, some point here, some point here and some point here. Now looking at this figure, can you quickly see uh which vertical barriers will have at least one point in the first quadrant?

[00:22:28]You can guess or you can just observe that if you place barrier something like this. If you if you place barrier below this point then no matter where you are placing this barrier one point will always be available on the first quadrant. Right? One point will always be available on the first quadrant. And if you place a barrier above it then of course no point will be no point will be present in the first quadrant. So one thing is for sure that you have to place the barrier below the maximum y on the left hand side for the first quadrant to not be empty.

[00:23:13]Now what about this? What about the case where you don't want the second uh what about the case where you want so these are the quadrants. So you know what you want to what you have to do in order to make sure that this is not empty. Now what about this case like how do you ensure that this case is not empty. So you can see that here even in all of these placements one point is always available in this uh the bottom left quadrant. But what is the case where it will not be available?

[00:23:47]So let's look at that case.

[00:23:54]Assume you you have this vertical barrier and assume that you have these these points some point here some point here some point here here here here and here then you can notice that if you place a barrier over here something is available on the bottom left even here it's available even here it's available even here it's available and so on. But if you place something like so, if you place the barrier after the smallest Y after the smallest vertic smallest Y that is available on the RHS, then this is your left quadrant bottom left quadrant and then nothing is present. So from the left side you can see that if you place barrier if you place the horizontal barriers in this region minimum value of y on the left hand side and the maximum value of y on the left hand side then the left hand side would be sorted for sure you don't have to worry about it.

[00:24:58]So this means that uh if you had this configuration let's say so this simplifies things for us because now we only have to focus on just two elements. So on the left hand side you just have to focus on what is the biggest element on the right hand side in terms of y because you have fixed x.

[00:25:25]That is how the barrier was created. And now you are wondering about why. So suppose this is the topmost point on the left hand side and this is the bottommost point on the left hand side.

[00:25:37]So one thing you know for sure that all the barriers have to be in this region only otherwise one of the quadrant will be missing.

[00:25:47]But what about the right hand side? So right hand side can also follow a similar will also follow a similar strategy but in isolation. So they could have something like this that their their highest peak is here and their bottom is over here. So they will be content if you place barriers only in this bigger region. But you have to make both of them happy. Why? Because when you are placing these barriers when you are placing these barriers then this and this should be filled but this and this should also be filled together at the same time. So from this figure what can you conclude? So if you if you say that this is the condition for LHS that you have to place the barrier in this range and from the RHS the barriers are in the range of minimum of Ystar let's say and maximum of Ystar and Ystar means that the Y's are coming from the right hand side of this split then you can see that if you place any barrier in between Then this works for the right hand side but does not work on the left hand side.

[00:27:03]This means that you can't take the minimum of both of them and then place the barrier. You will actually have to do this. The answer would be you have to place the barrier of maximum of the smallest left element and the smallest right element because the maximum of these two is this. So if you if you start placing barrier above this line then this would be happy because there is something below it and this entity will also be happy. And what about this quantity? So here also you can see that if you if you place a barrier like so then for on the left hand side the first quadrant has become empty. But if you take if you place a barrier like so then in the first quadrant this element has something and this section also has something. So you have to place the barrier in this region only. So you figure out what is the maximum of these two minimas and then what is the minimum of these two maxima. So biggest elements on the left hand side and the biggest element on the right hand side. So that is the entire algorithm for placing the barriers. So I hope you see why we are taking the minimum of both the maxima and the maximum of both the minima on the left hand side and the right hand side.

[00:28:31]So let's look at the code. So again you start with the old code and you try to optimize it. So this was the old code that we had and this time we were placing the barriers and then we were going over each points and then figuring out what is which quadrant it lies in.

[00:28:47]But this time in order for us to optimize it, we will first of all premputee what is the minima on the left hand side. You remember this we will premp compute.

[00:29:00]So once you have done the split you compute what is the minima on the left hand side. You call this as left y min and then left yax. This is the left yax.

[00:29:10]And then you compute the minima on the right hand side. Suppose it is this right y min and then you compute the min maxima on the right hand side which is this and then you take the maximum of both the minimas which is this region and the minimum of both the minimas maximas which is this region and you are allowed to place the barriers in between them. So since you were iterating over all the possible horizontal barriers, you can simply check if this horizontal barrier is between this global minima and maxima range that you have selected.

[00:29:49]If it is then the answer is yes. The this partition like this partition without even looking at any of the points you can confidently say that this partition will have at least one point in each of these quadrants. So you can see that the time complexity of this solution is O of N cube. Still it is O of N cube but now it is in in a way that we can optimize because now it deals with maximas and minimas. So let us see how to optimize this case. Now you can see that to optimize it. So once you have once you have placed this vertical barrier then all you are doing is you are looking towards all the elements on the left hand side and computing their minima and the maxima. Similarly, you are looking at all the elements on the right hand side and you are computing their minima and their maxima. And then while doing the operations, you are computing the maxima of the minimas and the minima of the maximas.

[00:30:50]But this computation you could you you can do beforehand because this is nothing but a prefix minima and prefix maxima. And this is nothing but a suffix minima and a suffix maxima on the sorted on the sorted array in terms of x values because you are trying to place the barriers one by one in increasing order of x. So all you have to do is you have to premp compute the prefix minima and the prefix maxima and suffix minima and the suffix maxima. This way when you when you are doing this operation again on on a particular vertical barrier you don't have to do this iteration again you can just compute what is your prefix minima and what is your suffix minima and you take the maximum of that and similarly for the maxima on the left hand side maxima on the right hand side and you take the minima of that and uh when you are doing this operation one thing you have to keep in mind that for this. So suppose this was created at x's. So on the left hand side of this suppose this element corresponds to x is equal to 3. So for x is equal to 3.

[00:32:05]There could be multiple copies of x is equal to 3. So three could exist with five and three could exist with 7 and so on. So that is why I have applied a fancy trick to figure out what is the index of the elements that we should be looking for in the suffix. So this finds that index and then it decides okay if this is the prefix maximum and then this is the suffix maximum what should the answer be. So with this the time complexity of the solution has become O of N². Now how do we optimize it even further?

[00:32:43]Now to optimize it even further let's look at what what we are actually doing.

[00:32:49]So for each for for a fixed x so for a fixed vertical uh barrier you are you are trying each possibility of x and you are checking whether this line falls in an interval or not. So if you call this interval X or let me call it if you call this global Y min as P and the global Y mix Y max as Q. So for each vertical line you are checking whether this vertical line is nothing but a value X. So you are checking is this true? You are asking this question. Is this true?

[00:33:35]But do you really need to iterate over all the elements to find out whether it is true or not? You don't really because if you know that you can you have your arrays with all the unique y values and if you sort all the arrays and let's say the y values are 2 3 5 9 7 13 and 25. And now here notice that when you are doing this comparison you are iterating over all the y's. It actually doesn't matter whether y came from the left hand side or from the right hand side. So assume that this is all the unique y values that you have in your array. Then what what currently what you are doing is you are picking two and you are asking this question. So you see that this global y min is fixed for a fixed xb this y min is fixed because if xb is fixed this is the if the x barrier is fixed then the prefix maxima and the suffix maximas they are also fixed. So you are picking two and you are asking is it is it in this interval p2q then you are picking three and you are asking is it in the in this interval p2q and so on. So that is why the time complexity is O of N. But you don't necessarily need to do that because all you are interested in is if you you are interested in this how many elements in this array lie in the interval P2Q and this is a very standard problem to solve via STL using lower bound. So your lower bound can give you how many elements of the array are less than or equal to Q and then you can find out how many elements of the array that are less than or equal to Q and then you can subtract them to get the number of elements in this array that are in this range P to Q. So if you do it in this manner then you already got your answer because you can see that the answer will be a subarray of the sorted array because if this is smaller than P then this is also smaller than P and if this is larger than Q this is also larger than Q. So all you have to do is you have to use the lower bound or upper bound from STL to figure out the count of elements in an array which lies in this interval.

[00:36:03]So you take the same code as before and previously you were doing the iteration manually with this for loop. This time you get rid of that for loop and you keep on placing the vertical barriers one by one. And once you have placed the vertical barrier you get what is the P and what is the Q and you find out the number of elements in this sorted Y array that lie in this range P to Q.

[00:36:31]And then now you can see that the time complexity has become O of N login. Why is this login coming? Because you are doing upper bound and upper bound basically tells you the number of elements that are less than or equal to the key that you have provided. And that is why the time complexity is O of LN.

[00:36:50]Now can you improve the time complexity even further? So yes there is also an O of N approach to this problem that we will discuss as the last part of the video. So for the O of N solution. So this time you want to find the O of N solution. So this is highly specific to the problem because in this version uh O of N solution only exists if the problem tells you that all the elements are between 0 to 10 ^ 6. So the problem that I was talking about it mentioned that x i and y i are up till 10 ^ 6. So if that is the case how do you avoid the binary search that you are doing over here via upper bound. You can see that since all the elements are up to 10 ^ 6 then you can just maintain an array of 10 ^ 6 and if you see an element if a particular y is present you set it as one else you set it as zero. Then if you want to count the number of integers in this range P to Q and P and Q will also of course be less than or equal to 10 ^ 6 then all you have to do is compute the this prefix sum this prefix sum and then subtract them to get this interval P2Q. So using prefix sums you can you can solve this problem in O of N. So this part will still remain and this is the prefix sum function that gives you the sum of any subarray of in O of one. And you keep the same code as before but this time you compute the count of elements in the range P to Q in the array using prefix sum and not binary search. But uh okay, I mean I wouldn't call it a real O of N optimization because this was highly specific to the problem. But I I just mentioned it because the editorial states that you have to solve it in O of N which I think is an overkill. No need to do that. But uh yeah, I hope you saw the ideas that we kind of used in this problem. So these kind of problems look very scary at first like in a contest you are terrified of attempting this because at first glance it looks like geometry problem and you might not have the skills to solve it but you saw that how just approaching it step by step by brute forcing it and then applying some optimization led us to the final of end solution and uh this is this is an okay problem I think it used prefix sum, prefix max, suffix max and then upper bound, lower bound and those kind of optimizations to solve. So I think this is uh this is a good problem for beginners although not that great but I think overall it's a decent problem. So let me know in the comment section how did you like this problem? Uh this appeared as problem D in the last code forces round and if you have any query about it let me know in the comment sections.