Welcome back.
Let's now discuss how we can solve this question.
Let's say that the array which is given to us three is three, seven, five, six, eight and four.
Now we have seen that we can visualize this in this manner.
Right.
So these are the vertical lines.
And the height over here is three.
The height over here is seven etc..
Now the first method that we are going to discuss over here is the brute force method.
And this just involves checking every possibility.
Right.
So we are going to take every set of two vertical lines.
And we're going to find the area.
And among all the possibilities we are going to take the area which gives us the maximum area.
All right.
So this is the brute force method.
Now initially we are going to have a variable and we are going to say max area is equal to zero.
All right.
So this is going to be a variable.
And then at each point we are going to check whether the new area is greater than the existing max area.
And if so we are going to update the max area to the new area.
All right.
Now for the brute force solution we are going to have two pointers, I and J.
Now initially I is going to point to three over here, which is the starting point, and J is going
to point at I plus one.
Now at this value of I we are going to check all these other cases.
Right.
So these are the possibilities three and seven, three and five, three and six, three and eight and
three and four.
Right.
So that is what we are going to do.
Now let me just write the indices over here.
All right.
So that's 0 to 5.
Now at this point when I is pointing to index zero and J is pointing to index one, we have the values
in the array as three and seven.
Right.
So visually we can see that we are taking these two lines.
Now in this case we have seen that we can fill water up to this point right.
Which is three.
Because if we fill water for a greater height than this, it will spill over right in this container.
So we have to take the minimum between 3 and 7.
And then this over here which is the width will be the difference between the indices.
Right.
J is pointing to one and I is pointing to zero.
So j minus I will give us one which is the width over here.
So this area over here will be the minimum between 3 and 7 into J minus I.
So that will give us the area.
So the minimum between 3 and 7 is equal to three.
And j minus I is one -0 which is one.
So over here we get the area as three three into one is three.
Now among zero and three three is greater right.
So we are going to update max area to three.
All right.
So we are done with that.
Now we are going to move J.
All right.
So we are going to move J to the index two over here.
And at this point we have the value three and five.
So we are considering this line over here and this line over here.
Now the area which we can form over here is this much right.
Which is minimum of three and five which is three into J minus I.
Right.
So minimum of three comma five into j minus I.
Now the minimum over here will be three because above that the water will spill over.
So the minimum over here is three.
And j minus I is two -0 which is equal to two.
So three into two gives us six.
Six is greater than the previous max area which is three.
So we update max area to six.
All right.
Now again we move forward.
We move J.
All right.
So we move J from 2 to 3.
So J comes over here.
Now we are again trying to find the area.
So the minimum between 3 and 6 is going to be three right.
And j minus I is three -0 which is three.
So the area at this point is three into three which is nine which is greater than six.
So we update the max area to nine.
Now we move forward.
All right.
So j now points to index four.
Now the minimum between 3 and 8.
That is three.
All right.
Now three into four -0 which is four.
So three into four gives us 12 which is greater than nine.
So we update it and we get max area is equal to 12.
Now again we move forward.
So j is equal to five at this point.
Now minimum between 3 and 4 is equal to three and five -0 is equal to five.
So the area is three into five which is equal to 15 which is greater than 12.
So we update the max area to 15.
All right.
So we have done all the possibilities for I is equal to zero.
So we move I to one at this point.
And for j is equal to 2 to 5.
We will keep comparing all the possibilities and check for the maximum area.
Now initially when I is equal to one and j is equal to two, the minimum is going to be five and two.
Minus one is equal to one.
So five into one is equal to five right.
So the all the possibilities are five and one.
Now when when we have five and six the minimum is six.
When we have sorry when we have seven and six right.
When we have seven and six, the minimum is six.
When we have seven and eight the minimum is seven.
When we have seven and four, the minimum is four.
Right.
And then we are going to have the j minus I values right.
In this case it's two minus one.
That's one three minus two.
That's two four minus one that's three and five minus one that's four.
So these are all the possibilities.
Now we can see that when we get to this we will not change the max area.
When we get to this 12 is still less than 15.
So we won't change the max area.
But when we get to this when we have seven into three, that's 21.
So we will update the max area because that's greater than 15 right.
So we get 21 over here.
And then after that when we get four into four which is 16, we don't change the max area.
So we have completed this iteration.
All right.
Now again we move I ahead.
So I comes to two and we check all these possibilities for J.
Right.
So that's the brute force method.
We are just checking all the possibilities.
So at this point it will be five into one.
This will be five into two.
And this will be four into three.
Right.
Because the minimum among five and four is three is four right.
So we have five into one, five into two and four into three.
And the areas are five, ten, 12 respectively.
And we can see that none of these is greater than 21.
Right.
So in none of these instances will be update the maximum area.
So it's still 21.
All right.
So we have completed this iteration.
Now again we change I from 2 to 3.
So I comes over here and J takes the values four and five.
So these are the two possibilities.
So we have six into one and four into two.
Right.
Because among six and eight six is the smaller and four minus three is one among six and four four is
the smaller and five minus three is two.
So the possible areas over here is six and eight which is not greater than 21.
So we don't change max area.
And we again move I to four.
And J only can take the value five, at which point the area is four, which is the minimum among eight
and four right into five minus four which is equal to one.
Again the area is just four which is not greater than 21.
So in this way we have found that the max area is equal to 21.
And we will just return 21 from the function, and we are getting 21 in this instance where I is over
here, right.
And J is over here.
So we are taking these two lines seven and eight.
In this case we can fill up to a height of seven.
And the width over here is 123.
This is three right.
And seven into three gives this area over here which is equal to 21.
All right.
So this is the brute force solution.
Now let's take a quick look at the complexity analysis of the brute force method.
The time complexity over here is going to be O of n square right.
Why is that.
So we can clearly see that we have two for loops right.
So it's a nested for loop.
We have for one for loop for moving the point of I the the position where I is pointing to.
And then we have another for loop, which for each instance of I will loop through the possibilities
of J.
So that gives us an idea that I is almost doing n operations.
And for each of these operations we are doing another N operations, which is the second for loop for
the for moving the position of J.
Right.
So this is one way of thinking about this.
Now you can think of it in this way.
Also when I is equal to zero, how many comparisons are we doing?
We are doing three and seven which is one, three and five, which is two, three and six, which is
three, three and eight, which is four and three and four, which is five.
So when I is.
Equal to zero.
We are doing five comparisons right now.
In this case n is equal to six.
So this five over here is actually n minus one.
So if n was ten, when I is equal to zero we would do nine comparisons.
Similarly when I is equal to one we will do four comparisons.
When I is equal to two, we will do three comparisons.
When I is equal to three, we will do two comparisons.
When I is equal to four, we will do finally one comparison.
And that ends it right.
So we won't move to I is equal to five because then we will not have any J.
So over here you can see that the number of operations that we are doing is actually n minus one plus
n minus two, etc. up to one.
So that's n minus one.
Plus N minus two, etc. up to one.
Now this actually sums up to n minus one into n minus one plus one by two, right?
So this is actually n minus one into n by two which is equal to n square minus n by two.
So the dominating factor is n square.
That's why we can say that the time complexity of this solution is o of n square.
Now how did I get this that n minus one plus n minus two etc. up to one that it is equal to n minus
one into n minus one plus one by two.
This is actually a concept from maths.
This is because this over here is an arithmetic progression right now.
Again, this is a good thing to know if you have the values one up to n one plus two plus three, etc.
if you're adding it up to n this over here, you can find it as n into n plus one by two.
So I'm just using this formula over here to find that n minus one plus n minus two, etc. up to one
is equal to n minus one into n minus one plus one by two.
How is that.
So notice over here the last term is n right.
And I'm doing n into one greater than the last term.
So in this case the last term is n minus one.
So I'm doing n minus one into one greater than n minus one which is n minus one plus one divided by
two.
So that is how we're getting this.
And this simplifies to n square minus n by two.
And over here the dominating factor is n square.
That's why the time complexity of this solution is O of n square.
All right.
So we have seen why the time complexity is O of n square.
What about the space complexity.
We are not using any extra space or any auxiliary space right.
So we are not using any extra space.
Therefore this function or this method runs in constant space which is O of one.