Welcome back.
Now over here we have the code which we just now wrote.
Now let's walk through it and let's take the input as 375684.
Right.
So this is the array which is given to us.
Let me write the indices over here zero, one, two, three, four and five.
All right.
So that's the input.
Now let's walk through the code.
What is happening over here.
First area is set to zero and we have two pointers.
Right eye is set to zero.
So I is over here.
And J is set to array dot length minus one which is over here.
The length is six six minus one is five.
So J is set over here.
Now as long as I is less than j we are going to loop right.
So that's the while loop over here.
Now we are going to check the minimum value among these two three and four.
The minimum is three right.
So we are going to find the new area which is three into J minus I which is five -0 which is five.
So the new area at this point is 15.
And then over here the area was zero.
So we are going to take the maximum value among zero and 15 to be area which is equal to 15.
So this is changing to 15.
And then we are going to check whether which among these two is lesser.
So we see that r I at I is less than array at j.
So therefore we are going to change the I pointer.
So we are going to increment it.
And I comes over here.
Now again I is less than J.
So again we loop through over here.
Now we are going to find the minimum among seven and four which is four right.
So we have four.
And then the difference between the pointers five and one is four.
So four into four is 16.
So we're going to change the array the area to 16.
So let me just write that over here.
We have area as 16.
And again we are going to check whether this is less than this which is not the case.
So we're going to change the j pointer.
So j minus minus.
So J comes over here right.
So J is over here.
Now again I is still less than J.
So I is over here at one and J is at four.
So I is less than J.
So we again loop through over here.
We are going to find the minimum between 7 and 8 which is seven.
And we're going to multiply this with j minus I which is four minus one which is three.
So seven into three gives us 21.
And that is greater than 16.
So we are going to change the value of area to 21 at this point.
Right.
The maximum of 16 and 21 which is 21.
Again we are going to check whether seven is less than eight.
Yes that's true.
Therefore we are going to change this pointer by doing I plus plus.
So I is pointing to this second index over here.
At this point now I is still less than J.
All right.
So we are going to take the minimum among five and eight which is five.
And we will multiply this with four minus two which is two.
So five into two is ten.
And among 21 and 1021 is the greater value.
So we don't change the area.
Now among five and eight we can see that five is less right.
So our at I is less than area j.
So we do I plus plus.
So I comes over here.
Now we are going to check again.
We are going to loop through again because I is less than J now among six and eight the minimum value
is six, right.
And then we are going to multiply it with four minus three which is one.
So six into one just is equal to six.
Now among 21 and 621 is greater.
So we don't change the area now among six and eight.
Yes you can see that six is less than eight.
So we do I plus plus.
So I comes over here right.
So I comes over here.
So I and J both are pointing at index four.
Now when we check over here I is not less than J right.
Four is not less than four.
So we come out of it and we are just going to return the area which is 21.
So this is how the function works which we have written.
Now we can see that we have done a lot less number of operations than the brute force solution.
Right.
So let's look at the time and space complexity of the solution.
Now the time complexity over here is O of N and the space complexity is O of one.
Now we can see that we went through the given array 375684.
That was the array, right?
We went through it only once.
We are touching every element only once, right.
So we can see that the time complexity is O of n.
Now if we look at the number of operations right.
So let's just quickly look at that as well.
We can see that we are doing only n by two operations.
So initially I is over here and J is over here.
So we are going to compare these two values.
Right now let's say we are always moving I now again we will only move the value which is minimum among
the two.
But always at every step we will move one of the pointers right.
So when it comes to the number of operations it does not matter.
So just to get a feeling.
So over here we have done one operation.
Now let's say we move the pointer again.
We do one operation.
We again move the pointer again.
We do one operation again we do.
We move the pointer, we do one more operation and we move the the pointer again.
And we do one more operation.
So you can see that if we have six elements over here, we are going to do five operations, which is
o n minus one operations.
And that is of the order of n.
So that's why we can say that we are doing N operations or the time complexity over here is O of n.
And again I'm just repeating it over here.
We will not always move the I pointer the pointer which is pointing at the value which is lower right.
Only that pointer will be moved right.
But again, whichever pointer is moved we will move that pointer.
And then there will be an operation which is finding the height which is minimum of minimum value when
among the two values right where the two pointers are pointing.
So we will take the minimum as the height.
And then we go ahead and do some constant time operations over here.
So we have seen that the time complexity over here is of the order of N, and the space complexity is
O of one, because we are not using any auxiliary space.