All language subtitles for 006 Thinking About Our Optimal Solution_en

So now we reach that crucial step where we ask, can we optimize our solution?

Going back to our code here, we know that we have a time complexity of of x squared and a space complexity

of of one.

The end squared is formed by our double for loop.

And when we did this in our first question, we were thinking of ways to increase our space in order

to decrease our time.

But we need to rationally think about this.

Is that same approach going to help us here?

And this is a very important thing because we need to actually think about what this question is asking

us and how our solution attempts to solve it.

What are we doing?

We are storing the max area that we've come across so far of every area that we calculate using P one

and P two.

So this double for loop does not separate because we need p one and p two together in order to figure

out the area.

And that's why we have no step in between these two for loops, which means that there's actually no

additional caching that can happen for p one.

This first for loop, what are the second for loop?

Is there anything we can do with memory in order to improve this process or even eliminate this for

loop as a whole?

Well, what we do is we calculate the height and width using these two P's, and then we get the area.

Then we essentially just check against the max error we've got so far and we see if we need to update

it.

But there really is nothing here that we're doing that would consume more memory because the moment

that we're done with this area, we don't need it anymore.

If we needed it and it was greater than what we had, then we would have stored it already.

But there's nothing here that we can do in order to scale our memory, in order to improve this process.

So what we did last time is not going to work here.

And that's a very important thing, because we need to really rationally think about this problem.

So what we do need to do that can improve this is actually learn a new technique which is known as shifting

pointers.

And let me show you what that is.

So here I have generated a new test case for us and I switched the pointers from P one and p two to

A and B to better match what we have in our formula.

And I want us to really think deeply.

Now, this new test case will help us understand this new concept.

But I also want to build upon the knowledge that we've gained so far from both our previous array question,

as well as what we've just done with our two pointers in our non optimal solution.

Let's first think back to our original array question.

The very first one we did.

If you remember, we were given some target value.

Let's say using the same array, that value was 13.

We know that when our first pointer is pointing at this value and our second pointer is pointing at

this value, four and nine, add together to give us 13.

And there we had our solution.

The key difference here is that the distance between A and B didn't matter with that question.

And B being on the opposite sides of the array has no impact on how we come to the solution for finding

our target.

In fact, this is easily demonstrated that if our target changed to be six.

This means that in order for a solution to work, B needs to be in this place here.

But this has no impact.

And B, being anywhere in our array doesn't change how we find our target.

But this is not the same case as our current question.

We know that with our current question, the width has a direct impact on the actual area.

We know that by looking at our equation, we can see immediately that the distance between A and B has

a direct impact on the value of the area that comes out of it, because that's the nature of multiplication.

The other thing we need to note, though, is that we don't really know whether or not it's increasing

or decreasing.

That will change this area outcome because it varies from a case to case basis.

It's not a guarantee that as long as A and B are greater distance apart, then somehow our area goes

up.

That's not the case.

We can actually see that directly in this current example, let's do the calculation for the area now

using the placement of A and B right here.

So the minimum between A and B is the minimum between four and nine.

So four is the minimum value.

As for B index minus eight index, that's five -0, which gives us five.

So four times five gives us 20.

But what happens if we move a forward buy one.

So let's move forward and do a new calculation.

We'll keep the 20 as a reference.

Amos forward to eight.

And now we have to recalculate the minimum between A and B.

So eight and nine is eight.

And B of I, which is five minus A, VI, which is one is five minus one, which gives us four, eight

times four gives us 32.

So automatically we can see that by shrinking the size of our width, we actually ended up with a larger

area.

So this leads us to our second point, which is that if we really think about what just happened, the

outcome of the area is impacted by the lesser of the two values of A and B.

We saw that by shrinking the distance between A and B, we somehow end up with a larger area, which

tells us that the only value in this part of the equation that has some impact on the outcome of the

area is the smaller value.

So let's just go back to what we had before.

We saw earlier what happens if we were to move our smaller value by increasing it?

We saw a direct transformation where the area got bigger.

But what about the larger value?

What about B?

Let's say we move B inwards.

What are the only possibilities that could happen for B?

Well, be either gets larger or it gets smaller.

So let's explore these two cases.

Let's say B got larger first.

So instead of three, just imagine it was 12.

When we were to plug this into our error calculation, what happens to the myth?

It's still going to be four against 12, which means that the number that comes out of this is still

four.

This means that even though B got bigger, there was no direct impact on our area calculation.

So now we know that if the larger number gets larger, it doesn't matter.

We don't even care about it.

But what happens if the larger number gets smaller?

So instead of let's say the 12, let's say we, it becomes the three in the place that it is right now.

So now the calculation becomes the mean of four and three, and now our min changes are min becomes

three.

So here we actually see that our area would have been smaller in this case because not only did we decrease

the value on this side, we've also decreased the value on this side.

So we know that for the larger value, the only case is that by changing its placement, we have somehow

decreased our total area.

And we don't want that.

We only want to figure out if we can maximize the area, if there's a way for us to increase the area

possible.

So now let's put these two ideas together.

We know that the only thing that really matters in comes to moving either A or B is trying to move the

smaller value forward and try and see if that somehow yields us a larger calculation.

And that's going to be the real crux of this optimal solution and this new technique, which is known

as the two shifting pointers.

So what we want to do is exactly what we have here.

We want to initialize two pointers, but we want to initialize them at the opposite sides of the array

because what we're doing is we're maximizing this value right here.

We want to get the biggest calculation possible for width because it does have an impact.

And we also want to make sure that as we shift our values, there is no possible way where the values

on the outskirts, meaning the opposing sides of our variables, could possibly give us a larger container.

So we just got to make sure of that.

And how we make sure of that is just by starting on the ends.

So now our calculation becomes what is the smaller of these two values?

We're going to calculate the area first of A and B.

So we did this calculation already, but let's just do it again.

But we're also going to keep track of the max area that we find so far very similar to what we did before.

And let's just say it's Max and it starts at zero.

So the minimum between four and nine is four and five -0, which is the indices is five.

So four times five is 20 and that's bigger than our max area.

So let's update that.

Next, let's move a forward.

Because A is the smaller value and as we mentioned, we only care about the smaller value.

Amos forward and now we get the men between eight and nine.

So this value is now eight.

And the distance is five minus one, which is four.

Eight times four is 32.

And we have a new max area of 32.

Now we have to shift the smaller over once more.

So A comes over and we do our calculation.

Once again, those min between one and nine is one, five minus two is three.

The area here is three.

Three is not bigger than 32.

So nothing happens in terms of our max area, but we shift our values over again.

And this time we do our calculation the exact same as we did last time.

The men between two and nine is two.

The distance is five minus three, which is two.

So this gives us a area of four for still not larger than 32.

So we do our a shift again, which is because it's the smaller number.

And now the men between three and nine is three, B and A is five minus four, which is one.

So once again, we get another container area of three.

Three is still smaller than 32, so our max area now is done.

We have no more room for any of our pointers to move because they've just come up against each other.

So now we have our answer.

32 is our maximum area.

The other thing that will notice is that we've also only touched each element once.

This means that we've managed to bring our time complexity down to zero of RN, which is a drastic improvement

from O of UN squared.

Every element will only be operated on once and then after that we are definitely moving one of our

two pointers.

We don't know which one, but one of them is moving, which means that at most we performed PN operations

on this array.

So this is the thing about two pointers.

The main key with the two pointers is that we have to think about how we move these two pointers when

it's considered done moving.

And also what is the rationale between determining which of them to move in the first place?

We were able to figure this out because we were able to see from our area calculation that the minimum

value between these two was the only one that actually directly had an impact on an area getting bigger.

The other thing was that we were able to see that the width had some factors to do with it because in

some ways when the width changes, these two values must change.

One of them has to change.

So we just had to figure out which one of them to change.

And by looking at this minimum value and how it affects the area, we could see that by moving the minimum

value.

That was how we could possibly end up with a larger area.

So then the optimization just became, okay, let's shrink our width on every operation, but then conditionally,

based on which value was smaller, would be the one that we shrunk.

And along the way we just calculate the area and store the max area the way that we've been doing before.

So I know that a lot of that is really new knowledge and this process of breaking down this equation

into the rational steps to do this is going to be one of the key things in critical thinking that we

need to work on and really thinking deeply about these things that seem at first very basic.

Because within them lie the chance for optimization when combined with these technical tricks such as

this two pointer style of problem solving.

And this course is really going to focus on these two things.

We're going to learn some of these technical tools that we just saw with the two pointers, but also

how do we build up a mental framework so that we can rationally break down what the rules are and how

we can best utilize these tools in order to deliver us an optimal solution.

So what I want you to do now is take what we've just seen and try and code it yourself.

It's going to be a little different from what we did with the four loops, but it's still good to give

it a try if you can't figure out how to do it.

No problem.

That's what we're going to do in the next video.