Hi everyone.
Let's now discuss how we can solve this question in a better manner.
Now again, let's say that the array which is given to us is three, seven, five, six, eight and
four.
Now let me write the indices of the array zero, one, two, three, four and five.
And we have seen that we can visualize this in this manner.
Right.
So at at index zero we have this line which has height three.
At index one we have this line, this vertical line which has height seven etc..
Now to solve this question in a better manner, we are going to use the two shifting pointers method.
Now we can use this method in many questions now.
So.
So this is a classic method for solving coding interview questions.
So in this we are going to have two pointers.
Now we are not going to check all the possibilities.
We are going to check the possibilities in an intelligent manner.
So let's see how we are going to solve this.
Now we know that the area when we take two lines, for example, if you take this line and this line,
the area is going to be the height in this case, which is the minimum among these two into the width,
right.
So area is equal to height into width.
All right.
Now how we are going to do is we are going to have two pointers such that we initially have the maximum
possible width.
For this we are going to have the pointers at the beginning and the end.
Right.
So in this case the width will be five -0 which is equal to five.
And that is the maximum possible width.
Now if we move the pointers to anywhere else for example if I move this to over here then the width
is five minus one which is four.
So it will reduce right.
So this over here this position over here is the position where the width is maximum.
All right.
Now what is the area.
At this point the area will be equal to the minimum of three and four into five -0.
Right.
So this will be the area at this position.
Now before we proceed and solve this question, let's make a few observations.
The first observation is that if you move the pointer the width will decrease.
We have already discussed that right.
So we have placed the the pointers in such a manner that the width is maximum.
Now we have these two pointers so we can move them in two directions right.
So I can either move this pointer in towards the right or I can move this pointer towards the left.
Let's think about both possibilities.
If I move 3 to 7 and if I move 4 to 8, can we make any observations among about the height right now?
What is what is to be noted over here among three and four?
Three is the minimum one.
Right.
So if I move the pointer which is pointing to the minimum value, and if I move the pointer which is
pointing to the maximum or the greater value among the two, right among the two values.
Now if we make this observation, you can see that if we move the pointer which is pointing to the minimum
value, there is a possibility for the height to increase.
But if we move the pointer which is pointing to the value, which is the greater among the two, the
height cannot increase, right?
Why is that?
So let's think about this for a moment.
Now let's say I'm moving this pointer over here right.
So I'm moving.
We are saying it cannot increase.
Now this value over here can either be greater than three or it can be less than three.
Right.
So if it is greater than three right it can be either greater than three or less than three.
This value over here and we are taking the case where we are moving this pointer.
Now if we are moving it over here, if it's greater than three, then the minimum among the two will
still be three, right.
So we are not increasing it.
Now.
If it is less than three still, then we will change the height to the lesser value.
Therefore the height is still not increasing.
Right.
So we can be sure that if we move the pointer which is pointing to the greater value, the height will
not increase.
It may stay constant or it may decrease, it will stay constant.
If this value is greater than three, it will decrease.
If this value which is over here is less than three.
Now what about moving this pointer over here.
Let's think about it.
Let me just clear this up.
Now this value over here.
What about this value.
If we move this pointer then there are two possibilities.
Right.
This value over here can either be greater than four or it can be less than four.
Right.
So because we are comparing it with this with this value when we change the value.
Now let's say we move this.
Now if this value is greater than four then because we have to take the minimum among this and this.
So in that instance the height is increasing.
Right now again there is a possibility that this is less than four.
It could be even less than three like one.
In that case the height is decreasing.
But there is at least a possibility for the height to increase.
So let's summarize.
If we move the pointer which is pointing to the lower value, there is a possibility for the height
to increase.
And when we move the pointer, the width is definitely decreasing.
But if we move the pointer which is pointing to the maximum among the two, then the height will not
increase.
So we have we have made these three observations over here.
All right.
Now because we want the maximum area and we are moving the we are changing the pointer.
Right.
We have one area.
We have to check the other possibilities now because we want the maximum area.
We have to move the pointer which is pointing to the minimum value because there is a possibility for
the height to increase.
Right.
So area is height into width.
Now if we are doing some change which reduces the width and ultimately we want the area to increase,
then the height has to increase, right.
So that is why we have to move the pointer which is pointing to the lower value.
All right.
So let's go ahead and do that and walk through the code.
And as we just go through one iteration it will become more clear.
Now let's say at this point we find the area we have the pointers at these two extremes.
The minimum among three and four is three and five.
-0 is equal to five.
So max area at this point is equal to 15.
Now because if we move the pointer which is pointing to the minimum among three and four, there is
a possibility for the height to increase.
Therefore let's move the pointer which is pointing to three.
So we move it to seven.
All right, so we have it over here.
Now let's find the area at this point, the minimum among seven and four.
Right.
Minimum among seven and four into five.
Minus one.
That's the new area.
Right?
So the minimum among seven and four is four and five minus one is four.
So four into four.
That gives us 16 right.
So this is four.
This is also four.
So four into four gives us 16.
So this is the area that we get.
And this over here is greater than this 15 over here.
Right.
So let's update the max area to 16.
All right.
Now the two pointers are pointing to seven and four.
Because of this logic.
Again we have to move the pointer which is pointing to the lower value which is four at this instance.
So let's move this to eight over here.
All right.
So we have it over here.
Now let's find the area.
At this point let me just make some space over here.
We have to find the minimum between 8 and 7 which is seven right.
Which is seven.
And we have to multiply it with four minus one which is three.
So seven into three gives us 21 which is the new area.
And that's greater than 16.
Therefore we update the max area to 21.
Now again we move the pointer which is pointing to the lower value which is seven in this case.
All right.
So we move the pointer to five over here.
Now among five and eight the minimum value is five.
So let's make some space over here.
The minimum value is five and four minus two is equal to two.
So the new area is five into two which is ten which is not greater than 21.
So we don't change the max area.
Again we move the pointer which is pointing to the minimum among these two, which is this one over
here.
Right.
So this pointer is shifted to six.
Now the minimum among these two is six and four minus three is equal to one.
So six into one the area is still six which is not greater than 21.
And we are done right.
Because when we again move this pointer this these two are going to overlap.
So the left pointer is no longer less than the right pointer.
So we are going to do this iteration which we just now discussed.
As long as the left pointer is less than the right pointer.
So that we have considered all the meaningful cases.
So by doing this we can see that by just passing through the array, once we were able to find the maximum
area which is 21.
All right.
So we have discussed the optimum solution over here.
Now let's quickly look at the complexity analysis of this solution.
The time complexity of this solution is equal to O of n because we are just touching each element one
time.
Right.
We're just touching it one time.
Now let's say we just had to move only one pointer.
For example.
Let's write it over here so that it will become more intuitive.
You can just visualize it.
Now what is it?
What is it that's happening at every instance?
We have two pointers and we are doing one operation of comparison.
So I'm just writing that over here.
And then we will move any one of the pointers and do one more operation.
So again we are moving the pointer which has the which is pointing to the lower value.
But just to make this easy, let's say that we are always moving this pointer.
So this comes over here again we do one comparison.
Then this comes over here again we do one comparison.
This comes over here again we do one comparison right.
And this comes over here.
And we do one more comparison and we stop.
So over here we have six elements.
So you can see that we are doing only five comparisons which is equal to n minus one.
Or the number of operations that we're doing is of the order of n.
All right.
So we can see that the time complexity of this solution is O of n.
Now what about the space complexity?
The space complexity of this solution is O of one.
Right.
Because we are not using any auxiliary space, we are not creating a new array or hash table, etc..
So the space complexity is O of one or this solution runs in constant space.