Welcome back, everyone.
So here we're back in lead coat and we're looking at the question, trapping rainwater.
This is number forty two on code.
It's the exact question we've just done here.
I've just pasted our code solution into the editor right here, and we're going to submit and see how
we do.
So here we see our run time is pretty bad, but our memory usage is pretty good, our memory usage is
above 90 percent.
So that's pretty optimal as far as runtime when the bottom 10 percent, maybe even a little worse.
And what we have to do is understand why.
So let's go back to our code.
What we want to do is identify the space and time complexity, so looking at the time complexity, first
we can see here that we have our for loop which iterates this P value across the entire array one time.
But when we iterate through what are we doing to every element while here we can see that we have to
while loops and these while loops iterate to the left and to the right of the array.
And what they do is they actually touch every element on their respective sides.
So our left pointer is iterating across the entire array from P all the way to the end.
And then our right pointer is doing the same thing, iterating across every element all the way to the
right.
So if you were to add what the left and the right p do is they iterate across the entire array, meaning
that they touch every single element one time.
And we do this for every single iteration of our P value due to our for loop running across the entire
area.
So what we see is that our time complexity is actually big of an squared because it's end times and
times.
So that gives us a pretty bad time complexity, but what about our space complexity?
Well, let's look at all the values that we're storing.
When we look at total water here, we see that this value is pretty static in the sense that it's not
a scaling storage.
We also see that for our left P right, P, Max left, Max right.
These are also non scaling memory, using variables, meaning that they only store some one value that
might change, but it doesn't increase at all.
Even if our inputs increase, neither of these values increase.
We can say the same thing about our current water, which is a single calculation, and then total water
updating.
Well, it's not an array.
It's not an object.
There's nothing here that's actually growing.
So we add all of these together and all of these are big o of one.
So even if that's the case, we can see that our space complexity is O of one.
So that is why our memory was so good on code, but then our time was so bad, so how can we optimize
this solution?
Well, let's go through those steps that were already familiar with that.
We've learned so far, if we look at time and we look at space complexity, we can try that technique
where we see if there is a space complexity optimization that we can do, where we increase the amount
of space we use.
But that'll somehow bring down the time.
But let's logically walk through our code and see if that even works.
So here we can see that our total water is not something that can benefit from storing multiple values,
it just stores the final answer.
So there's no benefit here in changing how this is being stored.
As for our for loop, we only have one, but the internal double while loop, is there any optimization
here using any of these pointer values that can actually say we were to trade this for something like
an array or an object that scales what that improve what we're able to finally get to?
Well, not really either.
Here we can see that the whole logic of this entire block is just to get the calculation for the water
at that current point of P.
So that's pretty much what all of this is doing as well, because this actually gets the amount of water
above every single point.
And then what we do is we finally add it to the total water.
So this block of logic here is the only thing that we could think about whether or not we can optimize
with our space.
But there's nothing really here either that would make sense to make a scaling memory using data model.
Instead, we got to think to that second array question we did, which is where we use the two pointers.
Now, let's just refresh ourselves on what it is that the two pointer technique did.
The two point technique was where we initialized some pointer on the left and some points are on the
right, and then we conditionally try to figure out what rationale was there for us to move one of these
pointers inwards.
And while we were moving them inwards, we were collecting some information that we had determined based
on our equation.
So here we actually see that we have pretty much the exact same pieces in order to do so.
In fact, we're already using two pointers right here.
We have two pointers initialized and some rationale that decides whether or not they move.
The only difference is that they move outwards rather than inwards.
As for the actual formula, we also have a formula right here, and this formula calculates some value
of water at a given point.
So is there a way for us to combine these two things together so that instead of iterating pointers
outwards, we iterate pointers inwards?
Well, in order for us to do that, we have to think about what this rationale is doing this code right
here that we have written and see if we can reverse engineer that into this two points of structure.
And to do that, we're going to have to think about the logic a little bit more clearly.
Let me just clear up some of this code so that we have a better idea of what I'm talking about.
So I've cleared away some of the code and I've left us with our original test array, our current water
calculation equation and then the graph representation of the array, what we need to do is figure out
how to implement two pointers and how to derive the logic required to properly transition from this
current equation that applies to one pointer to two.
So to do that, we need to think about the two pointers.
What are the main things we need to identify in order to properly implement this technique?
Well, the first one is that let's say we were to instantiate a pointer on the left and a pointer on
the right.
We need to conditionally move these pointers.
They don't just both move in.
At the same time, we have to think about some reasoning around why we would move one over another now
once we move a pointer where in some new iteration of our solution.
So once we're in that iteration, meaning that we have access to both the values at the pointers, but
also the values that we've seen with these pointers, what are we going to do in order to get closer
to our final solution, which in this case is getting the accumulated water inside of this array?
So we can actually get both of these answers by looking more closely at the equation that we have,
but this equation applies to the one pointer.
So let's just quickly review it so that we understand and see if we can break it apart and apply it
to this two points, your technique.
So we know that we iterate over some one pointer that scans across the array at any given point in the
array.
This points are then sends out a left pointer and a right pointer across the array in their respective
direction in order to figure out what is the maximum values that form the relevant container.
The most important thing to understand here is that the reason why we send out the pointers is to figure
out the two walls that actually form the final container for us to get the water at this current P value.
So if we think about that, let's think about how we can apply that to our two pointers.
So let's get rid of this first pointer here and let's put our two pointers back.
Let's say P left and P right.
If we think about the rationale behind this, the only thing that we know, if we have a pointer on
the left and the points on the right is that we have most likely two walls.
If we have the two walls available to us, what can we derive using these two pointers when they point
out the two walls?
Well, technically, we can't actually figure anything out, because when our pointers point to the
walls that we think must form a container, we know nothing about the information on the inside of these
two walls.
As you remember, the water content can be easily affected by any heights inside of the two walls that
form a container.
So imagine if we had let's say we were using this wall here.
Let's not pick this.
Let's pick this one so we can actually form some kind of wall if we pick this value.
So this one and this one, we don't actually know what's inside here until we scan into it with either
of these pointers.
We have no idea what the values of the heights in the middle are.
I know we can see it here, but just imagine if we didn't know because our code definitely doesn't know
until the pointer is actually touch those values.
So inside of here, it could be all very large values that form in such a way that using these two walls
as containers, no amount of water can be held inside.
That's a possibility.
So that means that we can't actually use these two pointers in order to single handedly figure out what
the walls are for some container and the water inside.
What we can keep track of, though, is the maximum values that they have respectively seen for each
side, meaning that we keep track of every value that people has seen when it scans through.
And we keep track of the maximum value that it's seen that is doing the same thing here, but what we
now need to decide is what do we do with that Max left Max right value that it's seen so far?
So we know that we want to keep track of a max left in a max right using the two pointers, but how
do we decide which one to move?
Well, what we also know is that using these two pointers, we had a very similar question in our last
max container water question where the smaller of the two walls was the one that we would move because
it was the only one that had a chance to actually impact the amount of water that was being stored.
Well, it's actually going to be the same logic in this question, but it's going to go a step further.
Now, the reason why we want to move the smaller value between the two pointers is because when we look
at this equation, we know that this equation is calculating for some current value, which before we
represented with some point Turpie.
Now that we don't have PE anymore, we actually need one of these two pointer values that we have to
take over that responsibility, the responsibility in this case is the one value that this equation
gets applied to, which means that the pointer that we do pick is going to be the one whose water we
calculate for.
It's also going to be the one whose height we use as current height.
Now, we need to join these two ideas together because our logic dictates that we need to decide on
the smaller value between the two to be the one that moves inwards.
But we also need to use the smaller value as the actual current height for this calculation.
And you'll see why once we actually step through the logic.
So here, let me just move our pointer back.
And what I'm also going to do is I'm going to initialize some Mac's left value, which is going to start
at zero and some max right value.
That's also going to start at zero.
And what we're going to do is we're going to logically walk through this between this zero value and
this to value which one's smaller while there's zero value is so we know that this is the lesser value
that we need to operate on.
Now, what we also need to decide now is do we try and calculate the amount of water for this value
or do we try and update our marks left?
The reason why we need to consider this is because for this value to be the actual one we decide to
calculate the water for, we need to have a max left value that is bigger than the current value.
This value can only have water above it if some wall to the left of it is actually greater than itself.
This logic is not exact same for the right side, because the moment we knew that this right value.
This far off right value, no matter where it is, it could be right here or it could be here.
It doesn't matter.
We know this value is bigger than this value.
That means that we know that this wall can be a wall on the right side, but we don't know if there's
a wall on the left side yet.
And the only way we can figure out if there is a wall on the left side of this valley to form a container
that allows us to calculate any water here is if this current value is smaller than the max left value
that we have.
And here we see that zero is not smaller than zero, so then nothing happens, then we can update Max
left equal to itself, which doesn't really change because Microsoft is currently zero anyways.
All we do is we move the pointer over.
So if that was confusing, we're going to go through more examples and hopefully they'll become more
clear.
So here we're going to see that now Max left is at one between the one and the two, which one is smaller
while the one is smaller.
So, again, we know that this one is going to be the one that we operate on.
Now, we also have to decide, do we calculate water for this value while using that same logic?
We know that we have a right wall.
This value we knew was larger than this value.
So for sure, this can be a wall.
What we also now need to figure out, though, is, is there a left wall to this current value?
Is the max left greater than our current value?
It's not.
So there's no possible way a wall could form on this side to give any water above this element.
So what we do then is we update Max left with the current value.
So now there's a value here, which is greater, which is one.
So we're going to update Max left to one and then we're going to move our pointer over again.
And now we once again ask between our left value and our right value of zero versus two, which on smaller
the left side zero, a smaller.
So now we know that this is the one we operate on, we decide, do we get current water or do we update
Max left?
Well, we know now that we see that our max left is greater than our current value.
So what we do then is we take Max left and we subtract it from our current height.
Now, you might be wondering why is it that we didn't do this check between a max left in a max, right?
Well, there's no need to because we know that as long as removing the pointer that's smaller, we're
always working with the lesser of the two values.
The lesser max is always going to be on the side of the element that's moving.
So here we know for sure that the right side is going to form a wall in order for this point to be moving.
Any value that we've iterated through must be smaller than the other side.
So now we know then that this side for sure is going to just take the max left value and then subtract
it from this value, because whatever side we're operating on is going to be the return from this Minne
statement anyways.
So then we just take Max left and we subtracted from the current height.
So one minus zero gives us one.
So then so far we have a water value of one.
So let's also keep track of a total water so far that we've seen.
So so far, total is equal to one.
Then we move this value over.
There's no need to update Max left because Max left was larger than our current value.
There's no way Max left would have been bigger with our current value anyways.
So then we move this value over and now we see OK, between these two, which one is smaller?
Well, they're actually equal.
So here we have to consider in a case where both values are equal.
Which side should we move?
In this case, let's just keep moving the left side, you can actually decide to move the right side,
it has no real impact on the solution.
You just have to choose one of them.
In this case, I'm going to choose to continue to move the left side.
So we say, OK, so we're going to move this left side again and we're going to ask, do we calculate
the water or do we update the max left?
So what we do, as we remember, is we compare the current max left versus our current value.
Is the max left bigger than our current value?
It's not so that we need to update Max left with our current value of two.
So I'm just going to update this to.
And I'm going to move this left pointer over.
Now that we're at this one, we once again check and say which between the two values is larger, two
is larger so than the blue left side is the one we operate on, which is a height of one.
And we have to decide, do we calculate the water or do we update the marks left?
In this case, we see that Max left is larger than our current value.
So we take Max left and we minus the current height using that same logic where we know the right side
wall was formed.
So we don't even need to do this in between the two masses.
We know for sure this wall must be greater than what we have.
The only wall that has an output is going to be the left Max, which is this two.
So, yes, they're both equal, but then our logic will still stand because it's still going to be this
side of the wall that impacts the overall height of this water level that it could be.
So we take this max left of two.
We subtracted from a current height of one.
We end up with one and we add it to our total.
So total becomes one plus one, which gives us two.
And then we move our pointer over and we do that same logical step again between the left and the right
side, which on a smaller well, the left side is smaller.
So we know that this side is the one we operate on.
We take this value and then we say, OK, we get the max left.
We want to calculate current water for it because it's smaller than Max left.
So it's Max left, minus the current value, which is zero.
So two minus zero gives us two two plus the current total of two gives us four total updates to four.
And then we move our pointer again.
And now the left pointer is at three.
So now we once again ask between the left and the right side, which side is smaller, the right side
is now smaller.
So we now know the right side is the one that we need to move or operate on.
So we ask, do we need to calculate the current water for the right side or do we want to update Max?
Right.
Well, here we see that two is not only greater than Max, right.
But we also know logically that there's no possible container that can be formed so that we can calculate
water here because there's no elements on the right side.
So then the right side moves over.
So right side moves over here, Max, right then gets updated to our value that we just saw, which
is to.
And now we once again ask, OK, between this value on this value, which value is smaller, this value
is smaller, so then we say, OK, do we want to calculate the water for this side or do we want to
update the max?
Right.
Well, we see that this value is smaller than Max.
Right.
Which means that we can form a container on any element on this right side, which in this case is the
max right value.
So this value we know the left value must be greater than this value in order for this to have moved
over.
So we don't even need to check them in between the max left in the max right.
We know for sure that whatever element we're currently on on the left side is greater than what's on
our current element that we're looking at, which is this right value.
So then it becomes the max, right, minus our current height of one, which gives us one.
So we add that to our total.
Which now gives us five and then we move this value over again.
And once again, we check between the left side and the right side, which side is smaller, the right
side a smaller, so the right side is the one we want to operate on.
So if this is the one we want to operate on, then let's calculate whether or not we want to move and
update Max.
Right.
Or if we want to calculate the current water while we see that our current value is less than any max.
Right, though that we have so that we know for sure that we can form some container.
So then it becomes the max.
Right, minus our current height to minus zero, which gives us to which then we add to our total,
bringing us up to seven.
That means that now we move our value once again over one more time and we do one more check between
our left value and our right value, which one is smaller?
The right value, a smaller one is smaller than three.
So then we know that the right value is the one we operate on.
So now we decide, do we want to update Max, right.
Or do we want to calculate current water while the max rate is currently larger than our current value?
So there's no need to update Max.
Right.
We need to calculate the current water.
The current water then becomes to minus our current height, which gives us one.
One added to our total, gives us eight.
So now we know that the total value is eight and we're done moving because now these two values have
bumped up against each other for this movie to move over there equal to the same value.
We have our answer.
We've calculated the total water in here.
Now, I know this was a much longer video, but this is a very, very important video because here we
see the difficulty of what the logical steps might take in order for us to go from a brute force to
an optimal solution.
This one requires us to make a lot of deeper connections in understanding how we went from that one
pointer example into this two pointer technique where we broke apart our one point, your formula to
still work for this, two points or one, it required us to understand deeply how these two pointers
could help us form some container for values on the inside.
But then figuring out which of these two pointers would actually be the value on the inside that we
could calculate for was the challenge.
So knowing that we could store some max left max right value, but also that the pointers themselves
had to emplace take the role of what he did as the current value that we were looking at for this calculation
is that big logical derivation that we have to make.
So if this was challenging, please watch this video again, because making those leaps is something
that we do have to work on.
It's the hardest thing in these technical interviews, in my opinion.
But the more we practice, the more we'll be able to make these mental connections and the better our
brain gets at taking what we have and then thinking deeply about what we currently do and seeing if
we can apply it to other techniques that we have learned.
So hopefully you can now understand how this works and try and figure out if you can code the solution
yourself.
This is definitely a great challenge to see if you truly understand all of the logical nuances of this
solution.
So maybe watch this video in order to refamiliarize yourself and see if you can write the code.
I definitely endeavor you to make that challenge to kodet it yourself.
If not, we're going to do it in the next video and I'll see you in the next video.