Welcome back.
Let's now take this sample input three, seven, five, six, eight and four.
Let me just write that over here.
Three, 7568 and four and walk through the code that we have just now written the brute force solution
to find the maximum area.
So this is the array.
All right.
And let's also write the indices over here.
This is zero.
This is one this is two this is three.
This is four and this is five.
All right.
Now initially area is equal to zero and I is over here.
This is where I is I is at zero.
And then we have J over here at I plus one which is over here.
Right now we are going to find the height which is the minimum among these two, which is what we do
over here.
Right.
So the minimum at this point is three.
And the width at this point is j minus I which is one -0 which is one.
So we get the area as three into one which is three.
And then the area at this point is zero.
So we are going to assign to area the maximum among zero and three which is equal to three right.
So this becomes three.
And then we are again incrementing I incrementing j right.
So j goes from here to here.
Now we are going to check the minimum among these two, which is again three, and we are going to multiply
it with the width which is two -0, which is two.
Right.
So we are getting six over here.
And then over here we are going to update the area to the maximum value among three and six which is
six.
Right.
So this becomes six over here.
And in this way we are going to continue with J.
Again we come over here and the minimum among these two is three.
And then the width over here is three -0 which is three.
So the area is nine.
So this gets updated to nine at this point over here again we move J.
We come over here.
Now the minimum among three and eight which is three and four -0 is equal to four.
So the area gets updated to 12.
Three into four is 12.
Again we come over here.
The minimum among three and four is three and the width is five -0 right.
So which is equal to five.
Now again the area gets updated to 15.
Now we are done with one round right.
So I was zero now and J has reached over here which is index five which is less than array dot length.
Array dot length is six.
Right.
So j no longer can go further.
And at this point we are going to change I right.
So I comes over here.
This is where I is at this point.
And we are going to increment through these values for J.
And we are going to continue.
So this is how the solution works over here.
And when we get I over here and once we get to J to this value which is eight, we will see that the
area is seven into four minus one which is three which gives us 21.
And that's the max area for this solution.
Now what about the time and space complexity for this solution?
Let's just make some space over here.
So it's pretty straightforward how this function works.
Now let's look at the time and space complexity again.
Now the time complexity for this solution is O of n square.
And the space complexity is O of one.
Now why the space complexity is O of one is pretty straightforward, right?
We're not using any extra space or any auxiliary space.
So the space complexity is O of one and the time complexity is O of n square because we have nested
for loops over here.
Right.
So I is going to go in this case let's just take this example.
Over here is 0123, four and five.
Right.
So I will go from 0 to 4.
Right.
And this is five right.
So I will go from 0 to 4.
When I is equal to zero J is going to take the values of 7 to 4 right which is one, two, three, four
and five.
So we're going to do five operations when I is equal to zero.
And I'm having one over here, two over here, three over here and four right.
Because I will go from 0 to 4.
Now let's take the worst case in this case J will go five values seven, five, six, eight and four.
That's five operations.
Now when I is equal to one that's I is over here J will go over these values which is four.
Right.
Similarly over here there will be three.
That is when I is over here there will J will take these three positions right.
These three values.
Similarly over here you have one.
And then you have one operation over here.
So the total number of operations you can see is five plus four plus three plus two plus one.
This five over here right.
This is n minus one.
Right n over here is six.
This is n minus one.
This is n minus two etc. up to one.
Now if you add these up right.
If you do n minus one plus n minus two up to one.
Right.
So this over here sums up to n minus one.
Into n minus one plus one divided by two.
Right.
So this over here, if you simplify it you will have a term with n square right.
If you just simplify this is nothing but n minus one into n divided by two.
Now if you simplify this you get n square minus n by two.
So this over here has the dominating factor of n square.
That's why we can say that the time complexity of this solution is O of n square.
So this is one way the mathematical way at looking at it or over here.
Also you can see that we have two for loops right.
So for every I again we are doing almost n operations over here.
Right.
So and then I also takes this almost n operations.
So that is also the intuitive way in which you can understand that the time complexity of this solution
is O of n square.