1
00:00:00,950 --> 00:00:02,030
Welcome back, everyone.

2
00:00:02,870 --> 00:00:07,010
So here we're back in lead coat and we're looking at the question, trapping rainwater.

3
00:00:07,220 --> 00:00:08,820
This is number forty two on code.

4
00:00:08,840 --> 00:00:11,080
It's the exact question we've just done here.

5
00:00:11,090 --> 00:00:17,180
I've just pasted our code solution into the editor right here, and we're going to submit and see how

6
00:00:17,180 --> 00:00:17,570
we do.

7
00:00:20,580 --> 00:00:26,400
So here we see our run time is pretty bad, but our memory usage is pretty good, our memory usage is

8
00:00:26,400 --> 00:00:27,420
above 90 percent.

9
00:00:27,430 --> 00:00:33,270
So that's pretty optimal as far as runtime when the bottom 10 percent, maybe even a little worse.

10
00:00:33,780 --> 00:00:36,330
And what we have to do is understand why.

11
00:00:37,220 --> 00:00:39,020
So let's go back to our code.

12
00:00:41,390 --> 00:00:49,130
What we want to do is identify the space and time complexity, so looking at the time complexity, first

13
00:00:49,370 --> 00:00:56,420
we can see here that we have our for loop which iterates this P value across the entire array one time.

14
00:00:57,200 --> 00:01:03,950
But when we iterate through what are we doing to every element while here we can see that we have to

15
00:01:03,950 --> 00:01:09,440
while loops and these while loops iterate to the left and to the right of the array.

16
00:01:10,220 --> 00:01:15,470
And what they do is they actually touch every element on their respective sides.

17
00:01:15,680 --> 00:01:21,580
So our left pointer is iterating across the entire array from P all the way to the end.

18
00:01:21,980 --> 00:01:27,530
And then our right pointer is doing the same thing, iterating across every element all the way to the

19
00:01:27,530 --> 00:01:27,800
right.

20
00:01:28,310 --> 00:01:35,270
So if you were to add what the left and the right p do is they iterate across the entire array, meaning

21
00:01:35,270 --> 00:01:39,050
that they touch every single element one time.

22
00:01:39,590 --> 00:01:46,330
And we do this for every single iteration of our P value due to our for loop running across the entire

23
00:01:46,330 --> 00:01:46,580
area.

24
00:01:47,060 --> 00:01:57,110
So what we see is that our time complexity is actually big of an squared because it's end times and

25
00:01:57,110 --> 00:01:57,890
times.

26
00:01:59,000 --> 00:02:04,250
So that gives us a pretty bad time complexity, but what about our space complexity?

27
00:02:04,700 --> 00:02:06,680
Well, let's look at all the values that we're storing.

28
00:02:07,580 --> 00:02:13,520
When we look at total water here, we see that this value is pretty static in the sense that it's not

29
00:02:13,520 --> 00:02:15,590
a scaling storage.

30
00:02:16,560 --> 00:02:21,250
We also see that for our left P right, P, Max left, Max right.

31
00:02:21,390 --> 00:02:29,430
These are also non scaling memory, using variables, meaning that they only store some one value that

32
00:02:29,430 --> 00:02:32,340
might change, but it doesn't increase at all.

33
00:02:32,580 --> 00:02:36,570
Even if our inputs increase, neither of these values increase.

34
00:02:37,260 --> 00:02:42,360
We can say the same thing about our current water, which is a single calculation, and then total water

35
00:02:42,360 --> 00:02:43,110
updating.

36
00:02:43,500 --> 00:02:44,700
Well, it's not an array.

37
00:02:44,700 --> 00:02:45,570
It's not an object.

38
00:02:45,580 --> 00:02:47,520
There's nothing here that's actually growing.

39
00:02:47,880 --> 00:02:52,310
So we add all of these together and all of these are big o of one.

40
00:02:52,800 --> 00:02:58,710
So even if that's the case, we can see that our space complexity is O of one.

41
00:02:59,920 --> 00:03:06,820
So that is why our memory was so good on code, but then our time was so bad, so how can we optimize

42
00:03:06,820 --> 00:03:07,540
this solution?

43
00:03:08,230 --> 00:03:11,830
Well, let's go through those steps that were already familiar with that.

44
00:03:11,830 --> 00:03:18,250
We've learned so far, if we look at time and we look at space complexity, we can try that technique

45
00:03:18,250 --> 00:03:25,090
where we see if there is a space complexity optimization that we can do, where we increase the amount

46
00:03:25,090 --> 00:03:26,020
of space we use.

47
00:03:26,020 --> 00:03:27,750
But that'll somehow bring down the time.

48
00:03:28,120 --> 00:03:31,330
But let's logically walk through our code and see if that even works.

49
00:03:32,410 --> 00:03:38,860
So here we can see that our total water is not something that can benefit from storing multiple values,

50
00:03:39,070 --> 00:03:41,110
it just stores the final answer.

51
00:03:41,230 --> 00:03:44,500
So there's no benefit here in changing how this is being stored.

52
00:03:45,340 --> 00:03:52,390
As for our for loop, we only have one, but the internal double while loop, is there any optimization

53
00:03:52,390 --> 00:03:58,900
here using any of these pointer values that can actually say we were to trade this for something like

54
00:03:58,900 --> 00:04:03,910
an array or an object that scales what that improve what we're able to finally get to?

55
00:04:04,600 --> 00:04:05,920
Well, not really either.

56
00:04:06,280 --> 00:04:12,580
Here we can see that the whole logic of this entire block is just to get the calculation for the water

57
00:04:12,610 --> 00:04:15,240
at that current point of P.

58
00:04:16,150 --> 00:04:21,280
So that's pretty much what all of this is doing as well, because this actually gets the amount of water

59
00:04:21,280 --> 00:04:22,330
above every single point.

60
00:04:22,630 --> 00:04:25,440
And then what we do is we finally add it to the total water.

61
00:04:25,750 --> 00:04:31,570
So this block of logic here is the only thing that we could think about whether or not we can optimize

62
00:04:31,570 --> 00:04:32,380
with our space.

63
00:04:32,980 --> 00:04:39,280
But there's nothing really here either that would make sense to make a scaling memory using data model.

64
00:04:39,730 --> 00:04:45,850
Instead, we got to think to that second array question we did, which is where we use the two pointers.

65
00:04:45,880 --> 00:04:49,960
Now, let's just refresh ourselves on what it is that the two pointer technique did.

66
00:04:51,230 --> 00:04:56,240
The two point technique was where we initialized some pointer on the left and some points are on the

67
00:04:56,240 --> 00:05:04,160
right, and then we conditionally try to figure out what rationale was there for us to move one of these

68
00:05:04,160 --> 00:05:05,480
pointers inwards.

69
00:05:06,270 --> 00:05:13,010
And while we were moving them inwards, we were collecting some information that we had determined based

70
00:05:13,010 --> 00:05:14,170
on our equation.

71
00:05:14,900 --> 00:05:20,060
So here we actually see that we have pretty much the exact same pieces in order to do so.

72
00:05:20,270 --> 00:05:23,660
In fact, we're already using two pointers right here.

73
00:05:24,230 --> 00:05:29,370
We have two pointers initialized and some rationale that decides whether or not they move.

74
00:05:29,780 --> 00:05:33,080
The only difference is that they move outwards rather than inwards.

75
00:05:33,830 --> 00:05:39,950
As for the actual formula, we also have a formula right here, and this formula calculates some value

76
00:05:39,950 --> 00:05:41,520
of water at a given point.

77
00:05:42,050 --> 00:05:47,840
So is there a way for us to combine these two things together so that instead of iterating pointers

78
00:05:47,930 --> 00:05:51,010
outwards, we iterate pointers inwards?

79
00:05:51,590 --> 00:05:56,690
Well, in order for us to do that, we have to think about what this rationale is doing this code right

80
00:05:56,690 --> 00:06:02,180
here that we have written and see if we can reverse engineer that into this two points of structure.

81
00:06:02,480 --> 00:06:06,140
And to do that, we're going to have to think about the logic a little bit more clearly.

82
00:06:06,350 --> 00:06:10,700
Let me just clear up some of this code so that we have a better idea of what I'm talking about.

83
00:06:11,870 --> 00:06:17,990
So I've cleared away some of the code and I've left us with our original test array, our current water

84
00:06:17,990 --> 00:06:24,770
calculation equation and then the graph representation of the array, what we need to do is figure out

85
00:06:24,770 --> 00:06:31,940
how to implement two pointers and how to derive the logic required to properly transition from this

86
00:06:31,940 --> 00:06:35,510
current equation that applies to one pointer to two.

87
00:06:36,140 --> 00:06:38,560
So to do that, we need to think about the two pointers.

88
00:06:38,780 --> 00:06:43,910
What are the main things we need to identify in order to properly implement this technique?

89
00:06:44,420 --> 00:06:48,710
Well, the first one is that let's say we were to instantiate a pointer on the left and a pointer on

90
00:06:48,710 --> 00:06:49,150
the right.

91
00:06:49,670 --> 00:06:52,600
We need to conditionally move these pointers.

92
00:06:52,610 --> 00:06:53,930
They don't just both move in.

93
00:06:53,930 --> 00:07:00,890
At the same time, we have to think about some reasoning around why we would move one over another now

94
00:07:00,890 --> 00:07:05,460
once we move a pointer where in some new iteration of our solution.

95
00:07:05,630 --> 00:07:11,630
So once we're in that iteration, meaning that we have access to both the values at the pointers, but

96
00:07:11,630 --> 00:07:16,370
also the values that we've seen with these pointers, what are we going to do in order to get closer

97
00:07:16,370 --> 00:07:22,130
to our final solution, which in this case is getting the accumulated water inside of this array?

98
00:07:23,310 --> 00:07:28,220
So we can actually get both of these answers by looking more closely at the equation that we have,

99
00:07:28,470 --> 00:07:30,780
but this equation applies to the one pointer.

100
00:07:30,780 --> 00:07:36,300
So let's just quickly review it so that we understand and see if we can break it apart and apply it

101
00:07:36,300 --> 00:07:37,580
to this two points, your technique.

102
00:07:38,400 --> 00:07:45,690
So we know that we iterate over some one pointer that scans across the array at any given point in the

103
00:07:45,690 --> 00:07:46,100
array.

104
00:07:46,150 --> 00:07:52,380
This points are then sends out a left pointer and a right pointer across the array in their respective

105
00:07:52,380 --> 00:07:59,810
direction in order to figure out what is the maximum values that form the relevant container.

106
00:08:00,270 --> 00:08:06,090
The most important thing to understand here is that the reason why we send out the pointers is to figure

107
00:08:06,090 --> 00:08:13,840
out the two walls that actually form the final container for us to get the water at this current P value.

108
00:08:14,610 --> 00:08:19,560
So if we think about that, let's think about how we can apply that to our two pointers.

109
00:08:19,890 --> 00:08:23,550
So let's get rid of this first pointer here and let's put our two pointers back.

110
00:08:23,790 --> 00:08:25,980
Let's say P left and P right.

111
00:08:27,650 --> 00:08:33,620
If we think about the rationale behind this, the only thing that we know, if we have a pointer on

112
00:08:33,620 --> 00:08:38,240
the left and the points on the right is that we have most likely two walls.

113
00:08:38,900 --> 00:08:45,650
If we have the two walls available to us, what can we derive using these two pointers when they point

114
00:08:45,650 --> 00:08:46,520
out the two walls?

115
00:08:47,030 --> 00:08:52,730
Well, technically, we can't actually figure anything out, because when our pointers point to the

116
00:08:52,730 --> 00:08:59,360
walls that we think must form a container, we know nothing about the information on the inside of these

117
00:08:59,360 --> 00:08:59,870
two walls.

118
00:09:00,380 --> 00:09:06,950
As you remember, the water content can be easily affected by any heights inside of the two walls that

119
00:09:06,950 --> 00:09:07,740
form a container.

120
00:09:08,060 --> 00:09:11,810
So imagine if we had let's say we were using this wall here.

121
00:09:11,810 --> 00:09:12,610
Let's not pick this.

122
00:09:13,110 --> 00:09:18,560
Let's pick this one so we can actually form some kind of wall if we pick this value.

123
00:09:18,590 --> 00:09:27,590
So this one and this one, we don't actually know what's inside here until we scan into it with either

124
00:09:27,590 --> 00:09:28,420
of these pointers.

125
00:09:28,430 --> 00:09:31,220
We have no idea what the values of the heights in the middle are.

126
00:09:31,550 --> 00:09:36,680
I know we can see it here, but just imagine if we didn't know because our code definitely doesn't know

127
00:09:36,680 --> 00:09:39,400
until the pointer is actually touch those values.

128
00:09:39,830 --> 00:09:46,700
So inside of here, it could be all very large values that form in such a way that using these two walls

129
00:09:46,700 --> 00:09:49,420
as containers, no amount of water can be held inside.

130
00:09:49,700 --> 00:09:51,060
That's a possibility.

131
00:09:51,560 --> 00:09:57,500
So that means that we can't actually use these two pointers in order to single handedly figure out what

132
00:09:57,500 --> 00:10:01,190
the walls are for some container and the water inside.

133
00:10:01,940 --> 00:10:08,750
What we can keep track of, though, is the maximum values that they have respectively seen for each

134
00:10:08,750 --> 00:10:14,840
side, meaning that we keep track of every value that people has seen when it scans through.

135
00:10:16,270 --> 00:10:22,450
And we keep track of the maximum value that it's seen that is doing the same thing here, but what we

136
00:10:22,450 --> 00:10:27,540
now need to decide is what do we do with that Max left Max right value that it's seen so far?

137
00:10:28,930 --> 00:10:33,520
So we know that we want to keep track of a max left in a max right using the two pointers, but how

138
00:10:33,520 --> 00:10:35,410
do we decide which one to move?

139
00:10:35,830 --> 00:10:43,390
Well, what we also know is that using these two pointers, we had a very similar question in our last

140
00:10:43,390 --> 00:10:49,090
max container water question where the smaller of the two walls was the one that we would move because

141
00:10:49,090 --> 00:10:55,330
it was the only one that had a chance to actually impact the amount of water that was being stored.

142
00:10:55,900 --> 00:11:01,010
Well, it's actually going to be the same logic in this question, but it's going to go a step further.

143
00:11:01,690 --> 00:11:09,040
Now, the reason why we want to move the smaller value between the two pointers is because when we look

144
00:11:09,040 --> 00:11:16,750
at this equation, we know that this equation is calculating for some current value, which before we

145
00:11:16,750 --> 00:11:19,690
represented with some point Turpie.

146
00:11:20,620 --> 00:11:27,730
Now that we don't have PE anymore, we actually need one of these two pointer values that we have to

147
00:11:27,730 --> 00:11:35,710
take over that responsibility, the responsibility in this case is the one value that this equation

148
00:11:35,710 --> 00:11:42,040
gets applied to, which means that the pointer that we do pick is going to be the one whose water we

149
00:11:42,040 --> 00:11:42,940
calculate for.

150
00:11:43,300 --> 00:11:46,760
It's also going to be the one whose height we use as current height.

151
00:11:47,680 --> 00:11:53,770
Now, we need to join these two ideas together because our logic dictates that we need to decide on

152
00:11:53,770 --> 00:11:57,070
the smaller value between the two to be the one that moves inwards.

153
00:11:57,320 --> 00:12:04,660
But we also need to use the smaller value as the actual current height for this calculation.

154
00:12:04,780 --> 00:12:07,500
And you'll see why once we actually step through the logic.

155
00:12:07,720 --> 00:12:09,940
So here, let me just move our pointer back.

156
00:12:10,570 --> 00:12:16,300
And what I'm also going to do is I'm going to initialize some Mac's left value, which is going to start

157
00:12:16,300 --> 00:12:18,940
at zero and some max right value.

158
00:12:18,940 --> 00:12:20,470
That's also going to start at zero.

159
00:12:21,370 --> 00:12:26,560
And what we're going to do is we're going to logically walk through this between this zero value and

160
00:12:26,560 --> 00:12:32,170
this to value which one's smaller while there's zero value is so we know that this is the lesser value

161
00:12:32,170 --> 00:12:33,280
that we need to operate on.

162
00:12:33,820 --> 00:12:39,640
Now, what we also need to decide now is do we try and calculate the amount of water for this value

163
00:12:40,390 --> 00:12:42,790
or do we try and update our marks left?

164
00:12:43,660 --> 00:12:50,170
The reason why we need to consider this is because for this value to be the actual one we decide to

165
00:12:50,170 --> 00:12:56,770
calculate the water for, we need to have a max left value that is bigger than the current value.

166
00:12:58,000 --> 00:13:05,530
This value can only have water above it if some wall to the left of it is actually greater than itself.

167
00:13:06,040 --> 00:13:11,500
This logic is not exact same for the right side, because the moment we knew that this right value.

168
00:13:12,380 --> 00:13:17,420
This far off right value, no matter where it is, it could be right here or it could be here.

169
00:13:17,900 --> 00:13:18,610
It doesn't matter.

170
00:13:18,620 --> 00:13:20,810
We know this value is bigger than this value.

171
00:13:21,740 --> 00:13:28,370
That means that we know that this wall can be a wall on the right side, but we don't know if there's

172
00:13:28,370 --> 00:13:29,470
a wall on the left side yet.

173
00:13:29,480 --> 00:13:34,700
And the only way we can figure out if there is a wall on the left side of this valley to form a container

174
00:13:34,820 --> 00:13:41,840
that allows us to calculate any water here is if this current value is smaller than the max left value

175
00:13:41,840 --> 00:13:42,500
that we have.

176
00:13:43,370 --> 00:13:49,190
And here we see that zero is not smaller than zero, so then nothing happens, then we can update Max

177
00:13:49,190 --> 00:13:53,300
left equal to itself, which doesn't really change because Microsoft is currently zero anyways.

178
00:13:53,630 --> 00:13:56,120
All we do is we move the pointer over.

179
00:13:57,420 --> 00:14:01,230
So if that was confusing, we're going to go through more examples and hopefully they'll become more

180
00:14:01,230 --> 00:14:01,650
clear.

181
00:14:02,520 --> 00:14:09,120
So here we're going to see that now Max left is at one between the one and the two, which one is smaller

182
00:14:09,510 --> 00:14:10,680
while the one is smaller.

183
00:14:10,710 --> 00:14:14,100
So, again, we know that this one is going to be the one that we operate on.

184
00:14:15,330 --> 00:14:20,470
Now, we also have to decide, do we calculate water for this value while using that same logic?

185
00:14:20,490 --> 00:14:21,810
We know that we have a right wall.

186
00:14:21,960 --> 00:14:24,030
This value we knew was larger than this value.

187
00:14:24,040 --> 00:14:25,670
So for sure, this can be a wall.

188
00:14:26,370 --> 00:14:31,890
What we also now need to figure out, though, is, is there a left wall to this current value?

189
00:14:32,370 --> 00:14:36,060
Is the max left greater than our current value?

190
00:14:36,490 --> 00:14:37,140
It's not.

191
00:14:37,140 --> 00:14:43,060
So there's no possible way a wall could form on this side to give any water above this element.

192
00:14:43,680 --> 00:14:46,950
So what we do then is we update Max left with the current value.

193
00:14:46,980 --> 00:14:49,530
So now there's a value here, which is greater, which is one.

194
00:14:49,920 --> 00:14:55,230
So we're going to update Max left to one and then we're going to move our pointer over again.

195
00:14:56,440 --> 00:15:03,100
And now we once again ask between our left value and our right value of zero versus two, which on smaller

196
00:15:03,610 --> 00:15:05,110
the left side zero, a smaller.

197
00:15:06,470 --> 00:15:11,690
So now we know that this is the one we operate on, we decide, do we get current water or do we update

198
00:15:11,690 --> 00:15:12,300
Max left?

199
00:15:13,010 --> 00:15:19,510
Well, we know now that we see that our max left is greater than our current value.

200
00:15:19,700 --> 00:15:23,750
So what we do then is we take Max left and we subtract it from our current height.

201
00:15:24,620 --> 00:15:30,150
Now, you might be wondering why is it that we didn't do this check between a max left in a max, right?

202
00:15:30,620 --> 00:15:35,960
Well, there's no need to because we know that as long as removing the pointer that's smaller, we're

203
00:15:35,960 --> 00:15:39,020
always working with the lesser of the two values.

204
00:15:39,350 --> 00:15:43,620
The lesser max is always going to be on the side of the element that's moving.

205
00:15:44,120 --> 00:15:49,460
So here we know for sure that the right side is going to form a wall in order for this point to be moving.

206
00:15:50,090 --> 00:15:53,760
Any value that we've iterated through must be smaller than the other side.

207
00:15:54,350 --> 00:16:00,770
So now we know then that this side for sure is going to just take the max left value and then subtract

208
00:16:00,770 --> 00:16:06,170
it from this value, because whatever side we're operating on is going to be the return from this Minne

209
00:16:06,210 --> 00:16:07,400
statement anyways.

210
00:16:07,730 --> 00:16:10,850
So then we just take Max left and we subtracted from the current height.

211
00:16:11,090 --> 00:16:14,040
So one minus zero gives us one.

212
00:16:14,630 --> 00:16:18,350
So then so far we have a water value of one.

213
00:16:18,980 --> 00:16:22,580
So let's also keep track of a total water so far that we've seen.

214
00:16:23,330 --> 00:16:25,580
So so far, total is equal to one.

215
00:16:27,200 --> 00:16:29,940
Then we move this value over.

216
00:16:29,990 --> 00:16:33,940
There's no need to update Max left because Max left was larger than our current value.

217
00:16:33,950 --> 00:16:36,910
There's no way Max left would have been bigger with our current value anyways.

218
00:16:37,430 --> 00:16:45,070
So then we move this value over and now we see OK, between these two, which one is smaller?

219
00:16:45,530 --> 00:16:46,790
Well, they're actually equal.

220
00:16:46,910 --> 00:16:50,420
So here we have to consider in a case where both values are equal.

221
00:16:50,810 --> 00:16:52,460
Which side should we move?

222
00:16:53,470 --> 00:16:57,510
In this case, let's just keep moving the left side, you can actually decide to move the right side,

223
00:16:57,520 --> 00:16:59,590
it has no real impact on the solution.

224
00:16:59,590 --> 00:17:00,930
You just have to choose one of them.

225
00:17:00,940 --> 00:17:03,450
In this case, I'm going to choose to continue to move the left side.

226
00:17:04,060 --> 00:17:10,000
So we say, OK, so we're going to move this left side again and we're going to ask, do we calculate

227
00:17:10,000 --> 00:17:12,860
the water or do we update the max left?

228
00:17:13,240 --> 00:17:17,620
So what we do, as we remember, is we compare the current max left versus our current value.

229
00:17:18,160 --> 00:17:20,020
Is the max left bigger than our current value?

230
00:17:20,500 --> 00:17:24,370
It's not so that we need to update Max left with our current value of two.

231
00:17:24,880 --> 00:17:27,100
So I'm just going to update this to.

232
00:17:29,030 --> 00:17:31,130
And I'm going to move this left pointer over.

233
00:17:33,270 --> 00:17:39,900
Now that we're at this one, we once again check and say which between the two values is larger, two

234
00:17:39,900 --> 00:17:44,660
is larger so than the blue left side is the one we operate on, which is a height of one.

235
00:17:44,670 --> 00:17:48,840
And we have to decide, do we calculate the water or do we update the marks left?

236
00:17:49,290 --> 00:17:52,940
In this case, we see that Max left is larger than our current value.

237
00:17:53,220 --> 00:17:58,200
So we take Max left and we minus the current height using that same logic where we know the right side

238
00:17:58,200 --> 00:17:59,030
wall was formed.

239
00:17:59,490 --> 00:18:02,670
So we don't even need to do this in between the two masses.

240
00:18:02,670 --> 00:18:05,700
We know for sure this wall must be greater than what we have.

241
00:18:06,150 --> 00:18:10,960
The only wall that has an output is going to be the left Max, which is this two.

242
00:18:11,790 --> 00:18:17,130
So, yes, they're both equal, but then our logic will still stand because it's still going to be this

243
00:18:17,130 --> 00:18:24,100
side of the wall that impacts the overall height of this water level that it could be.

244
00:18:24,870 --> 00:18:26,640
So we take this max left of two.

245
00:18:26,670 --> 00:18:28,500
We subtracted from a current height of one.

246
00:18:28,500 --> 00:18:31,080
We end up with one and we add it to our total.

247
00:18:31,380 --> 00:18:34,950
So total becomes one plus one, which gives us two.

248
00:18:35,890 --> 00:18:43,000
And then we move our pointer over and we do that same logical step again between the left and the right

249
00:18:43,000 --> 00:18:45,850
side, which on a smaller well, the left side is smaller.

250
00:18:46,240 --> 00:18:48,560
So we know that this side is the one we operate on.

251
00:18:49,090 --> 00:18:53,290
We take this value and then we say, OK, we get the max left.

252
00:18:53,320 --> 00:18:56,460
We want to calculate current water for it because it's smaller than Max left.

253
00:18:57,250 --> 00:19:00,970
So it's Max left, minus the current value, which is zero.

254
00:19:00,970 --> 00:19:08,020
So two minus zero gives us two two plus the current total of two gives us four total updates to four.

255
00:19:09,880 --> 00:19:12,520
And then we move our pointer again.

256
00:19:15,410 --> 00:19:17,460
And now the left pointer is at three.

257
00:19:17,870 --> 00:19:23,510
So now we once again ask between the left and the right side, which side is smaller, the right side

258
00:19:23,510 --> 00:19:24,280
is now smaller.

259
00:19:24,290 --> 00:19:28,720
So we now know the right side is the one that we need to move or operate on.

260
00:19:29,480 --> 00:19:34,880
So we ask, do we need to calculate the current water for the right side or do we want to update Max?

261
00:19:34,880 --> 00:19:35,190
Right.

262
00:19:35,780 --> 00:19:41,330
Well, here we see that two is not only greater than Max, right.

263
00:19:41,540 --> 00:19:47,030
But we also know logically that there's no possible container that can be formed so that we can calculate

264
00:19:47,030 --> 00:19:49,910
water here because there's no elements on the right side.

265
00:19:50,270 --> 00:19:52,040
So then the right side moves over.

266
00:19:53,680 --> 00:19:59,860
So right side moves over here, Max, right then gets updated to our value that we just saw, which

267
00:19:59,860 --> 00:20:00,400
is to.

268
00:20:02,130 --> 00:20:08,010
And now we once again ask, OK, between this value on this value, which value is smaller, this value

269
00:20:08,010 --> 00:20:14,460
is smaller, so then we say, OK, do we want to calculate the water for this side or do we want to

270
00:20:14,460 --> 00:20:15,440
update the max?

271
00:20:15,450 --> 00:20:15,910
Right.

272
00:20:16,710 --> 00:20:19,320
Well, we see that this value is smaller than Max.

273
00:20:19,320 --> 00:20:19,560
Right.

274
00:20:19,560 --> 00:20:24,000
Which means that we can form a container on any element on this right side, which in this case is the

275
00:20:24,000 --> 00:20:24,670
max right value.

276
00:20:24,690 --> 00:20:29,970
So this value we know the left value must be greater than this value in order for this to have moved

277
00:20:29,970 --> 00:20:30,390
over.

278
00:20:30,400 --> 00:20:34,090
So we don't even need to check them in between the max left in the max right.

279
00:20:34,560 --> 00:20:39,660
We know for sure that whatever element we're currently on on the left side is greater than what's on

280
00:20:39,660 --> 00:20:42,770
our current element that we're looking at, which is this right value.

281
00:20:43,470 --> 00:20:48,770
So then it becomes the max, right, minus our current height of one, which gives us one.

282
00:20:49,050 --> 00:20:50,730
So we add that to our total.

283
00:20:51,850 --> 00:20:57,940
Which now gives us five and then we move this value over again.

284
00:20:59,800 --> 00:21:05,980
And once again, we check between the left side and the right side, which side is smaller, the right

285
00:21:05,980 --> 00:21:09,000
side a smaller, so the right side is the one we want to operate on.

286
00:21:09,640 --> 00:21:14,800
So if this is the one we want to operate on, then let's calculate whether or not we want to move and

287
00:21:14,800 --> 00:21:15,520
update Max.

288
00:21:15,520 --> 00:21:15,910
Right.

289
00:21:16,090 --> 00:21:21,820
Or if we want to calculate the current water while we see that our current value is less than any max.

290
00:21:21,820 --> 00:21:26,130
Right, though that we have so that we know for sure that we can form some container.

291
00:21:26,410 --> 00:21:27,790
So then it becomes the max.

292
00:21:27,790 --> 00:21:33,190
Right, minus our current height to minus zero, which gives us to which then we add to our total,

293
00:21:33,190 --> 00:21:34,630
bringing us up to seven.

294
00:21:36,410 --> 00:21:42,650
That means that now we move our value once again over one more time and we do one more check between

295
00:21:42,650 --> 00:21:45,530
our left value and our right value, which one is smaller?

296
00:21:45,830 --> 00:21:48,720
The right value, a smaller one is smaller than three.

297
00:21:49,250 --> 00:21:51,860
So then we know that the right value is the one we operate on.

298
00:21:52,190 --> 00:21:54,870
So now we decide, do we want to update Max, right.

299
00:21:54,890 --> 00:21:59,730
Or do we want to calculate current water while the max rate is currently larger than our current value?

300
00:21:59,750 --> 00:22:01,100
So there's no need to update Max.

301
00:22:01,100 --> 00:22:01,380
Right.

302
00:22:01,400 --> 00:22:02,990
We need to calculate the current water.

303
00:22:03,290 --> 00:22:07,430
The current water then becomes to minus our current height, which gives us one.

304
00:22:07,700 --> 00:22:10,220
One added to our total, gives us eight.

305
00:22:10,940 --> 00:22:16,430
So now we know that the total value is eight and we're done moving because now these two values have

306
00:22:16,430 --> 00:22:20,260
bumped up against each other for this movie to move over there equal to the same value.

307
00:22:20,300 --> 00:22:21,260
We have our answer.

308
00:22:21,270 --> 00:22:23,330
We've calculated the total water in here.

309
00:22:24,140 --> 00:22:29,420
Now, I know this was a much longer video, but this is a very, very important video because here we

310
00:22:29,420 --> 00:22:36,530
see the difficulty of what the logical steps might take in order for us to go from a brute force to

311
00:22:36,530 --> 00:22:37,700
an optimal solution.

312
00:22:38,210 --> 00:22:44,060
This one requires us to make a lot of deeper connections in understanding how we went from that one

313
00:22:44,060 --> 00:22:52,160
pointer example into this two pointer technique where we broke apart our one point, your formula to

314
00:22:52,160 --> 00:22:59,510
still work for this, two points or one, it required us to understand deeply how these two pointers

315
00:22:59,510 --> 00:23:03,410
could help us form some container for values on the inside.

316
00:23:03,560 --> 00:23:08,330
But then figuring out which of these two pointers would actually be the value on the inside that we

317
00:23:08,330 --> 00:23:10,600
could calculate for was the challenge.

318
00:23:11,000 --> 00:23:16,220
So knowing that we could store some max left max right value, but also that the pointers themselves

319
00:23:16,220 --> 00:23:23,390
had to emplace take the role of what he did as the current value that we were looking at for this calculation

320
00:23:23,720 --> 00:23:27,690
is that big logical derivation that we have to make.

321
00:23:28,070 --> 00:23:33,650
So if this was challenging, please watch this video again, because making those leaps is something

322
00:23:33,650 --> 00:23:35,230
that we do have to work on.

323
00:23:35,420 --> 00:23:39,320
It's the hardest thing in these technical interviews, in my opinion.

324
00:23:39,920 --> 00:23:44,630
But the more we practice, the more we'll be able to make these mental connections and the better our

325
00:23:44,630 --> 00:23:53,210
brain gets at taking what we have and then thinking deeply about what we currently do and seeing if

326
00:23:53,210 --> 00:23:56,090
we can apply it to other techniques that we have learned.

327
00:23:56,960 --> 00:24:05,000
So hopefully you can now understand how this works and try and figure out if you can code the solution

328
00:24:05,000 --> 00:24:05,460
yourself.

329
00:24:05,870 --> 00:24:11,930
This is definitely a great challenge to see if you truly understand all of the logical nuances of this

330
00:24:11,930 --> 00:24:12,470
solution.

331
00:24:12,800 --> 00:24:17,840
So maybe watch this video in order to refamiliarize yourself and see if you can write the code.

332
00:24:17,870 --> 00:24:21,820
I definitely endeavor you to make that challenge to kodet it yourself.

333
00:24:22,130 --> 00:24:25,820
If not, we're going to do it in the next video and I'll see you in the next video.