1
00:00:00,860 --> 00:00:01,820
Hi everyone.

2
00:00:01,820 --> 00:00:06,020
Let's now discuss how we can solve this question in a better manner.

3
00:00:06,050 --> 00:00:11,060
Now again, let's say that the array which is given to us is three, seven, five, six, eight and

4
00:00:11,060 --> 00:00:11,540
four.

5
00:00:11,570 --> 00:00:16,040
Now let me write the indices of the array zero, one, two, three, four and five.

6
00:00:16,040 --> 00:00:19,100
And we have seen that we can visualize this in this manner.

7
00:00:19,100 --> 00:00:19,430
Right.

8
00:00:19,430 --> 00:00:23,300
So at at index zero we have this line which has height three.

9
00:00:23,450 --> 00:00:27,800
At index one we have this line, this vertical line which has height seven etc..

10
00:00:27,800 --> 00:00:33,860
Now to solve this question in a better manner, we are going to use the two shifting pointers method.

11
00:00:33,860 --> 00:00:36,890
Now we can use this method in many questions now.

12
00:00:36,890 --> 00:00:36,980
So.

13
00:00:36,980 --> 00:00:40,490
So this is a classic method for solving coding interview questions.

14
00:00:40,490 --> 00:00:43,190
So in this we are going to have two pointers.

15
00:00:43,190 --> 00:00:45,800
Now we are not going to check all the possibilities.

16
00:00:45,800 --> 00:00:49,280
We are going to check the possibilities in an intelligent manner.

17
00:00:49,280 --> 00:00:51,380
So let's see how we are going to solve this.

18
00:00:51,380 --> 00:00:56,510
Now we know that the area when we take two lines, for example, if you take this line and this line,

19
00:00:56,510 --> 00:01:02,000
the area is going to be the height in this case, which is the minimum among these two into the width,

20
00:01:02,000 --> 00:01:02,300
right.

21
00:01:02,300 --> 00:01:04,760
So area is equal to height into width.

22
00:01:04,820 --> 00:01:05,480
All right.

23
00:01:05,480 --> 00:01:11,630
Now how we are going to do is we are going to have two pointers such that we initially have the maximum

24
00:01:11,630 --> 00:01:12,740
possible width.

25
00:01:13,010 --> 00:01:16,310
For this we are going to have the pointers at the beginning and the end.

26
00:01:16,340 --> 00:01:16,670
Right.

27
00:01:16,670 --> 00:01:21,410
So in this case the width will be five -0 which is equal to five.

28
00:01:21,410 --> 00:01:23,450
And that is the maximum possible width.

29
00:01:23,900 --> 00:01:29,420
Now if we move the pointers to anywhere else for example if I move this to over here then the width

30
00:01:29,420 --> 00:01:30,980
is five minus one which is four.

31
00:01:30,980 --> 00:01:32,450
So it will reduce right.

32
00:01:32,450 --> 00:01:37,280
So this over here this position over here is the position where the width is maximum.

33
00:01:37,280 --> 00:01:37,880
All right.

34
00:01:37,910 --> 00:01:39,230
Now what is the area.

35
00:01:39,230 --> 00:01:45,530
At this point the area will be equal to the minimum of three and four into five -0.

36
00:01:45,530 --> 00:01:45,830
Right.

37
00:01:45,830 --> 00:01:48,050
So this will be the area at this position.

38
00:01:48,050 --> 00:01:53,210
Now before we proceed and solve this question, let's make a few observations.

39
00:01:53,570 --> 00:01:58,400
The first observation is that if you move the pointer the width will decrease.

40
00:01:58,400 --> 00:01:59,900
We have already discussed that right.

41
00:01:59,900 --> 00:02:04,610
So we have placed the the pointers in such a manner that the width is maximum.

42
00:02:04,610 --> 00:02:08,990
Now we have these two pointers so we can move them in two directions right.

43
00:02:08,990 --> 00:02:14,750
So I can either move this pointer in towards the right or I can move this pointer towards the left.

44
00:02:14,750 --> 00:02:16,940
Let's think about both possibilities.

45
00:02:16,940 --> 00:02:25,820
If I move 3 to 7 and if I move 4 to 8, can we make any observations among about the height right now?

46
00:02:25,820 --> 00:02:29,180
What is what is to be noted over here among three and four?

47
00:02:29,180 --> 00:02:30,500
Three is the minimum one.

48
00:02:30,500 --> 00:02:30,800
Right.

49
00:02:30,800 --> 00:02:36,530
So if I move the pointer which is pointing to the minimum value, and if I move the pointer which is

50
00:02:36,530 --> 00:02:41,780
pointing to the maximum or the greater value among the two, right among the two values.

51
00:02:41,780 --> 00:02:48,500
Now if we make this observation, you can see that if we move the pointer which is pointing to the minimum

52
00:02:48,500 --> 00:02:52,430
value, there is a possibility for the height to increase.

53
00:02:52,430 --> 00:02:58,070
But if we move the pointer which is pointing to the value, which is the greater among the two, the

54
00:02:58,070 --> 00:03:00,110
height cannot increase, right?

55
00:03:00,110 --> 00:03:00,710
Why is that?

56
00:03:00,710 --> 00:03:02,510
So let's think about this for a moment.

57
00:03:02,510 --> 00:03:05,840
Now let's say I'm moving this pointer over here right.

58
00:03:05,840 --> 00:03:07,220
So I'm moving.

59
00:03:07,220 --> 00:03:08,750
We are saying it cannot increase.

60
00:03:08,750 --> 00:03:14,060
Now this value over here can either be greater than three or it can be less than three.

61
00:03:14,060 --> 00:03:14,390
Right.

62
00:03:14,390 --> 00:03:19,430
So if it is greater than three right it can be either greater than three or less than three.

63
00:03:19,430 --> 00:03:23,300
This value over here and we are taking the case where we are moving this pointer.

64
00:03:23,300 --> 00:03:28,490
Now if we are moving it over here, if it's greater than three, then the minimum among the two will

65
00:03:28,490 --> 00:03:29,540
still be three, right.

66
00:03:29,540 --> 00:03:31,400
So we are not increasing it.

67
00:03:31,400 --> 00:03:31,970
Now.

68
00:03:31,970 --> 00:03:37,940
If it is less than three still, then we will change the height to the lesser value.

69
00:03:37,940 --> 00:03:40,580
Therefore the height is still not increasing.

70
00:03:40,580 --> 00:03:40,940
Right.

71
00:03:40,940 --> 00:03:47,690
So we can be sure that if we move the pointer which is pointing to the greater value, the height will

72
00:03:47,690 --> 00:03:48,800
not increase.

73
00:03:48,800 --> 00:03:53,000
It may stay constant or it may decrease, it will stay constant.

74
00:03:53,000 --> 00:03:55,730
If this value is greater than three, it will decrease.

75
00:03:55,730 --> 00:03:58,220
If this value which is over here is less than three.

76
00:03:58,220 --> 00:04:00,410
Now what about moving this pointer over here.

77
00:04:00,410 --> 00:04:01,160
Let's think about it.

78
00:04:01,160 --> 00:04:02,390
Let me just clear this up.

79
00:04:02,390 --> 00:04:04,100
Now this value over here.

80
00:04:04,100 --> 00:04:05,360
What about this value.

81
00:04:05,360 --> 00:04:09,290
If we move this pointer then there are two possibilities.

82
00:04:09,290 --> 00:04:09,590
Right.

83
00:04:09,590 --> 00:04:14,810
This value over here can either be greater than four or it can be less than four.

84
00:04:14,810 --> 00:04:15,230
Right.

85
00:04:15,230 --> 00:04:19,220
So because we are comparing it with this with this value when we change the value.

86
00:04:19,220 --> 00:04:20,600
Now let's say we move this.

87
00:04:20,600 --> 00:04:26,990
Now if this value is greater than four then because we have to take the minimum among this and this.

88
00:04:26,990 --> 00:04:30,020
So in that instance the height is increasing.

89
00:04:30,020 --> 00:04:34,100
Right now again there is a possibility that this is less than four.

90
00:04:34,100 --> 00:04:36,260
It could be even less than three like one.

91
00:04:36,260 --> 00:04:38,090
In that case the height is decreasing.

92
00:04:38,090 --> 00:04:42,710
But there is at least a possibility for the height to increase.

93
00:04:42,710 --> 00:04:44,390
So let's summarize.

94
00:04:44,390 --> 00:04:49,790
If we move the pointer which is pointing to the lower value, there is a possibility for the height

95
00:04:49,790 --> 00:04:50,510
to increase.

96
00:04:50,510 --> 00:04:54,440
And when we move the pointer, the width is definitely decreasing.

97
00:04:54,440 --> 00:04:59,840
But if we move the pointer which is pointing to the maximum among the two, then the height will not

98
00:04:59,840 --> 00:05:00,020
increase.

99
00:05:00,480 --> 00:05:04,110
So we have we have made these three observations over here.

100
00:05:04,140 --> 00:05:04,620
All right.

101
00:05:04,650 --> 00:05:10,710
Now because we want the maximum area and we are moving the we are changing the pointer.

102
00:05:10,710 --> 00:05:11,010
Right.

103
00:05:11,010 --> 00:05:12,060
We have one area.

104
00:05:12,060 --> 00:05:16,290
We have to check the other possibilities now because we want the maximum area.

105
00:05:16,290 --> 00:05:22,890
We have to move the pointer which is pointing to the minimum value because there is a possibility for

106
00:05:22,890 --> 00:05:24,060
the height to increase.

107
00:05:24,390 --> 00:05:24,780
Right.

108
00:05:24,780 --> 00:05:27,090
So area is height into width.

109
00:05:27,090 --> 00:05:33,210
Now if we are doing some change which reduces the width and ultimately we want the area to increase,

110
00:05:33,210 --> 00:05:35,310
then the height has to increase, right.

111
00:05:35,310 --> 00:05:40,800
So that is why we have to move the pointer which is pointing to the lower value.

112
00:05:40,800 --> 00:05:41,250
All right.

113
00:05:41,250 --> 00:05:43,950
So let's go ahead and do that and walk through the code.

114
00:05:43,950 --> 00:05:47,400
And as we just go through one iteration it will become more clear.

115
00:05:47,400 --> 00:05:53,760
Now let's say at this point we find the area we have the pointers at these two extremes.

116
00:05:53,760 --> 00:05:56,430
The minimum among three and four is three and five.

117
00:05:56,430 --> 00:05:58,020
-0 is equal to five.

118
00:05:58,020 --> 00:06:01,350
So max area at this point is equal to 15.

119
00:06:01,350 --> 00:06:06,360
Now because if we move the pointer which is pointing to the minimum among three and four, there is

120
00:06:06,360 --> 00:06:08,400
a possibility for the height to increase.

121
00:06:08,400 --> 00:06:12,360
Therefore let's move the pointer which is pointing to three.

122
00:06:12,360 --> 00:06:13,740
So we move it to seven.

123
00:06:14,570 --> 00:06:16,160
All right, so we have it over here.

124
00:06:16,190 --> 00:06:20,690
Now let's find the area at this point, the minimum among seven and four.

125
00:06:20,690 --> 00:06:20,930
Right.

126
00:06:20,930 --> 00:06:24,980
Minimum among seven and four into five.

127
00:06:24,980 --> 00:06:25,880
Minus one.

128
00:06:27,190 --> 00:06:28,300
That's the new area.

129
00:06:28,300 --> 00:06:28,570
Right?

130
00:06:28,570 --> 00:06:32,890
So the minimum among seven and four is four and five minus one is four.

131
00:06:32,890 --> 00:06:34,390
So four into four.

132
00:06:34,390 --> 00:06:36,460
That gives us 16 right.

133
00:06:36,460 --> 00:06:37,540
So this is four.

134
00:06:37,570 --> 00:06:38,620
This is also four.

135
00:06:38,620 --> 00:06:41,110
So four into four gives us 16.

136
00:06:41,110 --> 00:06:42,610
So this is the area that we get.

137
00:06:42,610 --> 00:06:45,790
And this over here is greater than this 15 over here.

138
00:06:45,790 --> 00:06:46,180
Right.

139
00:06:46,180 --> 00:06:48,910
So let's update the max area to 16.

140
00:06:49,450 --> 00:06:49,990
All right.

141
00:06:49,990 --> 00:06:53,230
Now the two pointers are pointing to seven and four.

142
00:06:53,230 --> 00:06:54,640
Because of this logic.

143
00:06:54,640 --> 00:07:00,430
Again we have to move the pointer which is pointing to the lower value which is four at this instance.

144
00:07:00,430 --> 00:07:02,770
So let's move this to eight over here.

145
00:07:03,070 --> 00:07:03,430
All right.

146
00:07:03,430 --> 00:07:04,690
So we have it over here.

147
00:07:04,690 --> 00:07:06,820
Now let's find the area.

148
00:07:06,820 --> 00:07:09,370
At this point let me just make some space over here.

149
00:07:09,880 --> 00:07:14,590
We have to find the minimum between 8 and 7 which is seven right.

150
00:07:14,590 --> 00:07:15,460
Which is seven.

151
00:07:15,460 --> 00:07:18,970
And we have to multiply it with four minus one which is three.

152
00:07:18,970 --> 00:07:23,080
So seven into three gives us 21 which is the new area.

153
00:07:23,080 --> 00:07:24,970
And that's greater than 16.

154
00:07:24,970 --> 00:07:27,970
Therefore we update the max area to 21.

155
00:07:27,970 --> 00:07:33,130
Now again we move the pointer which is pointing to the lower value which is seven in this case.

156
00:07:33,130 --> 00:07:33,520
All right.

157
00:07:33,520 --> 00:07:35,980
So we move the pointer to five over here.

158
00:07:35,980 --> 00:07:39,820
Now among five and eight the minimum value is five.

159
00:07:39,820 --> 00:07:41,650
So let's make some space over here.

160
00:07:41,650 --> 00:07:46,690
The minimum value is five and four minus two is equal to two.

161
00:07:46,720 --> 00:07:51,220
So the new area is five into two which is ten which is not greater than 21.

162
00:07:51,220 --> 00:07:53,230
So we don't change the max area.

163
00:07:53,230 --> 00:07:57,820
Again we move the pointer which is pointing to the minimum among these two, which is this one over

164
00:07:57,820 --> 00:07:57,970
here.

165
00:07:57,970 --> 00:07:58,240
Right.

166
00:07:58,240 --> 00:08:00,490
So this pointer is shifted to six.

167
00:08:00,490 --> 00:08:05,080
Now the minimum among these two is six and four minus three is equal to one.

168
00:08:05,080 --> 00:08:10,000
So six into one the area is still six which is not greater than 21.

169
00:08:10,000 --> 00:08:10,990
And we are done right.

170
00:08:10,990 --> 00:08:15,280
Because when we again move this pointer this these two are going to overlap.

171
00:08:15,280 --> 00:08:19,090
So the left pointer is no longer less than the right pointer.

172
00:08:19,090 --> 00:08:22,150
So we are going to do this iteration which we just now discussed.

173
00:08:22,150 --> 00:08:25,420
As long as the left pointer is less than the right pointer.

174
00:08:25,420 --> 00:08:28,240
So that we have considered all the meaningful cases.

175
00:08:28,240 --> 00:08:34,900
So by doing this we can see that by just passing through the array, once we were able to find the maximum

176
00:08:34,900 --> 00:08:36,970
area which is 21.

177
00:08:37,240 --> 00:08:37,690
All right.

178
00:08:37,690 --> 00:08:40,780
So we have discussed the optimum solution over here.

179
00:08:40,780 --> 00:08:44,380
Now let's quickly look at the complexity analysis of this solution.

180
00:08:44,380 --> 00:08:50,890
The time complexity of this solution is equal to O of n because we are just touching each element one

181
00:08:50,890 --> 00:08:51,190
time.

182
00:08:51,190 --> 00:08:51,550
Right.

183
00:08:51,550 --> 00:08:53,230
We're just touching it one time.

184
00:08:53,590 --> 00:08:57,670
Now let's say we just had to move only one pointer.

185
00:08:57,670 --> 00:08:58,210
For example.

186
00:08:58,210 --> 00:09:01,180
Let's write it over here so that it will become more intuitive.

187
00:09:01,180 --> 00:09:02,800
You can just visualize it.

188
00:09:02,800 --> 00:09:03,970
Now what is it?

189
00:09:04,210 --> 00:09:06,550
What is it that's happening at every instance?

190
00:09:06,550 --> 00:09:10,120
We have two pointers and we are doing one operation of comparison.

191
00:09:10,120 --> 00:09:11,650
So I'm just writing that over here.

192
00:09:11,650 --> 00:09:15,580
And then we will move any one of the pointers and do one more operation.

193
00:09:15,580 --> 00:09:19,960
So again we are moving the pointer which has the which is pointing to the lower value.

194
00:09:19,960 --> 00:09:23,710
But just to make this easy, let's say that we are always moving this pointer.

195
00:09:23,710 --> 00:09:26,530
So this comes over here again we do one comparison.

196
00:09:26,530 --> 00:09:29,470
Then this comes over here again we do one comparison.

197
00:09:29,470 --> 00:09:32,200
This comes over here again we do one comparison right.

198
00:09:32,200 --> 00:09:33,430
And this comes over here.

199
00:09:33,430 --> 00:09:35,680
And we do one more comparison and we stop.

200
00:09:35,680 --> 00:09:37,450
So over here we have six elements.

201
00:09:37,450 --> 00:09:42,100
So you can see that we are doing only five comparisons which is equal to n minus one.

202
00:09:42,100 --> 00:09:46,090
Or the number of operations that we're doing is of the order of n.

203
00:09:46,090 --> 00:09:46,810
All right.

204
00:09:47,410 --> 00:09:51,160
So we can see that the time complexity of this solution is O of n.

205
00:09:51,160 --> 00:09:53,290
Now what about the space complexity?

206
00:09:53,290 --> 00:09:56,020
The space complexity of this solution is O of one.

207
00:09:56,020 --> 00:09:56,380
Right.

208
00:09:56,380 --> 00:10:02,050
Because we are not using any auxiliary space, we are not creating a new array or hash table, etc..

209
00:10:02,050 --> 00:10:06,760
So the space complexity is O of one or this solution runs in constant space.