1
00:00:00,870 --> 00:00:01,950
Welcome back.

2
00:00:01,980 --> 00:00:05,130
Let's now discuss how we can solve this question.

3
00:00:05,130 --> 00:00:10,950
Let's say that the array which is given to us three is three, seven, five, six, eight and four.

4
00:00:10,950 --> 00:00:13,950
Now we have seen that we can visualize this in this manner.

5
00:00:13,950 --> 00:00:14,340
Right.

6
00:00:14,340 --> 00:00:15,870
So these are the vertical lines.

7
00:00:15,870 --> 00:00:17,400
And the height over here is three.

8
00:00:17,400 --> 00:00:19,260
The height over here is seven etc..

9
00:00:19,290 --> 00:00:24,030
Now the first method that we are going to discuss over here is the brute force method.

10
00:00:24,030 --> 00:00:27,270
And this just involves checking every possibility.

11
00:00:27,270 --> 00:00:27,600
Right.

12
00:00:27,600 --> 00:00:31,380
So we are going to take every set of two vertical lines.

13
00:00:31,380 --> 00:00:32,970
And we're going to find the area.

14
00:00:32,970 --> 00:00:38,670
And among all the possibilities we are going to take the area which gives us the maximum area.

15
00:00:38,670 --> 00:00:39,120
All right.

16
00:00:39,120 --> 00:00:40,770
So this is the brute force method.

17
00:00:40,770 --> 00:00:46,920
Now initially we are going to have a variable and we are going to say max area is equal to zero.

18
00:00:46,920 --> 00:00:47,220
All right.

19
00:00:47,220 --> 00:00:48,630
So this is going to be a variable.

20
00:00:48,630 --> 00:00:55,170
And then at each point we are going to check whether the new area is greater than the existing max area.

21
00:00:55,170 --> 00:00:58,920
And if so we are going to update the max area to the new area.

22
00:00:58,920 --> 00:00:59,520
All right.

23
00:00:59,550 --> 00:01:04,290
Now for the brute force solution we are going to have two pointers, I and J.

24
00:01:04,410 --> 00:01:10,470
Now initially I is going to point to three over here, which is the starting point, and J is going

25
00:01:10,470 --> 00:01:12,150
to point at I plus one.

26
00:01:12,540 --> 00:01:17,700
Now at this value of I we are going to check all these other cases.

27
00:01:17,700 --> 00:01:17,910
Right.

28
00:01:17,910 --> 00:01:22,950
So these are the possibilities three and seven, three and five, three and six, three and eight and

29
00:01:22,950 --> 00:01:23,610
three and four.

30
00:01:23,610 --> 00:01:23,970
Right.

31
00:01:23,970 --> 00:01:25,650
So that is what we are going to do.

32
00:01:25,650 --> 00:01:27,930
Now let me just write the indices over here.

33
00:01:27,960 --> 00:01:28,410
All right.

34
00:01:28,410 --> 00:01:29,760
So that's 0 to 5.

35
00:01:29,760 --> 00:01:37,170
Now at this point when I is pointing to index zero and J is pointing to index one, we have the values

36
00:01:37,170 --> 00:01:38,970
in the array as three and seven.

37
00:01:38,970 --> 00:01:39,330
Right.

38
00:01:39,330 --> 00:01:42,270
So visually we can see that we are taking these two lines.

39
00:01:42,270 --> 00:01:46,740
Now in this case we have seen that we can fill water up to this point right.

40
00:01:46,740 --> 00:01:47,580
Which is three.

41
00:01:47,580 --> 00:01:53,430
Because if we fill water for a greater height than this, it will spill over right in this container.

42
00:01:53,430 --> 00:01:57,090
So we have to take the minimum between 3 and 7.

43
00:01:57,090 --> 00:02:02,010
And then this over here which is the width will be the difference between the indices.

44
00:02:02,010 --> 00:02:02,370
Right.

45
00:02:02,370 --> 00:02:05,430
J is pointing to one and I is pointing to zero.

46
00:02:05,430 --> 00:02:09,690
So j minus I will give us one which is the width over here.

47
00:02:09,690 --> 00:02:16,590
So this area over here will be the minimum between 3 and 7 into J minus I.

48
00:02:16,620 --> 00:02:18,150
So that will give us the area.

49
00:02:18,150 --> 00:02:21,330
So the minimum between 3 and 7 is equal to three.

50
00:02:21,330 --> 00:02:24,810
And j minus I is one -0 which is one.

51
00:02:24,810 --> 00:02:28,380
So over here we get the area as three three into one is three.

52
00:02:28,410 --> 00:02:31,320
Now among zero and three three is greater right.

53
00:02:31,320 --> 00:02:34,560
So we are going to update max area to three.

54
00:02:35,040 --> 00:02:35,580
All right.

55
00:02:35,580 --> 00:02:36,840
So we are done with that.

56
00:02:36,840 --> 00:02:38,370
Now we are going to move J.

57
00:02:38,370 --> 00:02:38,760
All right.

58
00:02:38,760 --> 00:02:42,900
So we are going to move J to the index two over here.

59
00:02:42,900 --> 00:02:45,810
And at this point we have the value three and five.

60
00:02:45,810 --> 00:02:48,960
So we are considering this line over here and this line over here.

61
00:02:48,960 --> 00:02:51,900
Now the area which we can form over here is this much right.

62
00:02:51,900 --> 00:02:56,730
Which is minimum of three and five which is three into J minus I.

63
00:02:56,760 --> 00:02:56,970
Right.

64
00:02:56,970 --> 00:03:00,030
So minimum of three comma five into j minus I.

65
00:03:00,060 --> 00:03:04,260
Now the minimum over here will be three because above that the water will spill over.

66
00:03:04,260 --> 00:03:06,030
So the minimum over here is three.

67
00:03:06,030 --> 00:03:09,420
And j minus I is two -0 which is equal to two.

68
00:03:09,450 --> 00:03:11,100
So three into two gives us six.

69
00:03:11,100 --> 00:03:14,100
Six is greater than the previous max area which is three.

70
00:03:14,100 --> 00:03:16,350
So we update max area to six.

71
00:03:16,740 --> 00:03:17,130
All right.

72
00:03:17,160 --> 00:03:18,960
Now again we move forward.

73
00:03:18,960 --> 00:03:20,070
We move J.

74
00:03:20,070 --> 00:03:20,430
All right.

75
00:03:20,430 --> 00:03:22,140
So we move J from 2 to 3.

76
00:03:22,140 --> 00:03:23,520
So J comes over here.

77
00:03:24,660 --> 00:03:27,630
Now we are again trying to find the area.

78
00:03:27,630 --> 00:03:30,750
So the minimum between 3 and 6 is going to be three right.

79
00:03:30,750 --> 00:03:34,290
And j minus I is three -0 which is three.

80
00:03:34,290 --> 00:03:38,880
So the area at this point is three into three which is nine which is greater than six.

81
00:03:38,880 --> 00:03:41,190
So we update the max area to nine.

82
00:03:41,190 --> 00:03:42,360
Now we move forward.

83
00:03:42,360 --> 00:03:42,720
All right.

84
00:03:42,720 --> 00:03:45,180
So j now points to index four.

85
00:03:45,180 --> 00:03:46,950
Now the minimum between 3 and 8.

86
00:03:46,950 --> 00:03:47,760
That is three.

87
00:03:47,760 --> 00:03:48,180
All right.

88
00:03:48,210 --> 00:03:50,820
Now three into four -0 which is four.

89
00:03:50,820 --> 00:03:53,970
So three into four gives us 12 which is greater than nine.

90
00:03:53,970 --> 00:03:57,210
So we update it and we get max area is equal to 12.

91
00:03:57,210 --> 00:03:58,830
Now again we move forward.

92
00:03:58,830 --> 00:04:01,230
So j is equal to five at this point.

93
00:04:01,230 --> 00:04:06,510
Now minimum between 3 and 4 is equal to three and five -0 is equal to five.

94
00:04:06,510 --> 00:04:11,160
So the area is three into five which is equal to 15 which is greater than 12.

95
00:04:11,160 --> 00:04:13,860
So we update the max area to 15.

96
00:04:13,860 --> 00:04:14,520
All right.

97
00:04:14,520 --> 00:04:19,470
So we have done all the possibilities for I is equal to zero.

98
00:04:19,470 --> 00:04:21,960
So we move I to one at this point.

99
00:04:21,960 --> 00:04:24,870
And for j is equal to 2 to 5.

100
00:04:24,870 --> 00:04:29,370
We will keep comparing all the possibilities and check for the maximum area.

101
00:04:29,370 --> 00:04:36,390
Now initially when I is equal to one and j is equal to two, the minimum is going to be five and two.

102
00:04:36,390 --> 00:04:37,590
Minus one is equal to one.

103
00:04:37,590 --> 00:04:40,110
So five into one is equal to five right.

104
00:04:40,110 --> 00:04:43,380
So the all the possibilities are five and one.

105
00:04:43,380 --> 00:04:46,800
Now when when we have five and six the minimum is six.

106
00:04:46,800 --> 00:04:49,860
When we have sorry when we have seven and six right.

107
00:04:49,860 --> 00:04:51,930
When we have seven and six, the minimum is six.

108
00:04:51,930 --> 00:04:54,630
When we have seven and eight the minimum is seven.

109
00:04:54,630 --> 00:04:57,090
When we have seven and four, the minimum is four.

110
00:04:57,090 --> 00:04:57,570
Right.

111
00:04:57,570 --> 00:05:01,770
And then we are going to have the j minus I values right.

112
00:05:01,770 --> 00:05:03,060
In this case it's two minus one.

113
00:05:03,060 --> 00:05:04,470
That's one three minus two.

114
00:05:04,470 --> 00:05:08,580
That's two four minus one that's three and five minus one that's four.

115
00:05:08,580 --> 00:05:10,530
So these are all the possibilities.

116
00:05:10,530 --> 00:05:14,640
Now we can see that when we get to this we will not change the max area.

117
00:05:14,640 --> 00:05:17,400
When we get to this 12 is still less than 15.

118
00:05:17,400 --> 00:05:19,050
So we won't change the max area.

119
00:05:19,050 --> 00:05:22,500
But when we get to this when we have seven into three, that's 21.

120
00:05:22,500 --> 00:05:25,920
So we will update the max area because that's greater than 15 right.

121
00:05:25,920 --> 00:05:27,720
So we get 21 over here.

122
00:05:27,720 --> 00:05:32,580
And then after that when we get four into four which is 16, we don't change the max area.

123
00:05:32,580 --> 00:05:34,620
So we have completed this iteration.

124
00:05:34,620 --> 00:05:35,040
All right.

125
00:05:35,070 --> 00:05:37,020
Now again we move I ahead.

126
00:05:37,020 --> 00:05:40,950
So I comes to two and we check all these possibilities for J.

127
00:05:40,950 --> 00:05:41,160
Right.

128
00:05:41,160 --> 00:05:42,810
So that's the brute force method.

129
00:05:42,810 --> 00:05:44,880
We are just checking all the possibilities.

130
00:05:44,880 --> 00:05:47,160
So at this point it will be five into one.

131
00:05:47,160 --> 00:05:48,540
This will be five into two.

132
00:05:48,540 --> 00:05:50,160
And this will be four into three.

133
00:05:50,160 --> 00:05:50,460
Right.

134
00:05:50,460 --> 00:05:53,670
Because the minimum among five and four is three is four right.

135
00:05:53,670 --> 00:05:57,300
So we have five into one, five into two and four into three.

136
00:05:57,300 --> 00:06:00,150
And the areas are five, ten, 12 respectively.

137
00:06:00,150 --> 00:06:03,120
And we can see that none of these is greater than 21.

138
00:06:03,120 --> 00:06:03,300
Right.

139
00:06:03,300 --> 00:06:07,410
So in none of these instances will be update the maximum area.

140
00:06:07,410 --> 00:06:08,760
So it's still 21.

141
00:06:08,760 --> 00:06:09,270
All right.

142
00:06:09,270 --> 00:06:11,130
So we have completed this iteration.

143
00:06:11,130 --> 00:06:14,040
Now again we change I from 2 to 3.

144
00:06:14,040 --> 00:06:17,700
So I comes over here and J takes the values four and five.

145
00:06:17,700 --> 00:06:19,320
So these are the two possibilities.

146
00:06:19,320 --> 00:06:21,960
So we have six into one and four into two.

147
00:06:21,960 --> 00:06:22,440
Right.

148
00:06:22,440 --> 00:06:28,650
Because among six and eight six is the smaller and four minus three is one among six and four four is

149
00:06:28,650 --> 00:06:31,170
the smaller and five minus three is two.

150
00:06:31,200 --> 00:06:36,090
So the possible areas over here is six and eight which is not greater than 21.

151
00:06:36,090 --> 00:06:37,740
So we don't change max area.

152
00:06:37,740 --> 00:06:39,930
And we again move I to four.

153
00:06:39,930 --> 00:06:46,200
And J only can take the value five, at which point the area is four, which is the minimum among eight

154
00:06:46,200 --> 00:06:49,500
and four right into five minus four which is equal to one.

155
00:06:49,500 --> 00:06:52,830
Again the area is just four which is not greater than 21.

156
00:06:52,830 --> 00:06:57,570
So in this way we have found that the max area is equal to 21.

157
00:06:57,570 --> 00:07:05,100
And we will just return 21 from the function, and we are getting 21 in this instance where I is over

158
00:07:05,100 --> 00:07:05,940
here, right.

159
00:07:05,940 --> 00:07:07,710
And J is over here.

160
00:07:07,710 --> 00:07:11,070
So we are taking these two lines seven and eight.

161
00:07:11,070 --> 00:07:14,040
In this case we can fill up to a height of seven.

162
00:07:14,040 --> 00:07:16,440
And the width over here is 123.

163
00:07:16,440 --> 00:07:17,310
This is three right.

164
00:07:17,310 --> 00:07:21,840
And seven into three gives this area over here which is equal to 21.

165
00:07:22,080 --> 00:07:22,380
All right.

166
00:07:22,380 --> 00:07:24,330
So this is the brute force solution.

167
00:07:24,330 --> 00:07:29,520
Now let's take a quick look at the complexity analysis of the brute force method.

168
00:07:29,550 --> 00:07:33,780
The time complexity over here is going to be O of n square right.

169
00:07:33,780 --> 00:07:34,440
Why is that.

170
00:07:34,440 --> 00:07:37,440
So we can clearly see that we have two for loops right.

171
00:07:37,440 --> 00:07:38,790
So it's a nested for loop.

172
00:07:38,790 --> 00:07:45,630
We have for one for loop for moving the point of I the the position where I is pointing to.

173
00:07:45,630 --> 00:07:51,300
And then we have another for loop, which for each instance of I will loop through the possibilities

174
00:07:51,300 --> 00:07:51,900
of J.

175
00:07:51,900 --> 00:07:56,460
So that gives us an idea that I is almost doing n operations.

176
00:07:56,460 --> 00:08:02,310
And for each of these operations we are doing another N operations, which is the second for loop for

177
00:08:02,310 --> 00:08:04,080
the for moving the position of J.

178
00:08:04,080 --> 00:08:04,500
Right.

179
00:08:04,500 --> 00:08:06,510
So this is one way of thinking about this.

180
00:08:06,510 --> 00:08:08,310
Now you can think of it in this way.

181
00:08:08,310 --> 00:08:13,740
Also when I is equal to zero, how many comparisons are we doing?

182
00:08:13,740 --> 00:08:18,810
We are doing three and seven which is one, three and five, which is two, three and six, which is

183
00:08:18,810 --> 00:08:23,220
three, three and eight, which is four and three and four, which is five.

184
00:08:23,220 --> 00:08:23,940
So when I is.

185
00:08:24,050 --> 00:08:24,740
Equal to zero.

186
00:08:24,740 --> 00:08:26,900
We are doing five comparisons right now.

187
00:08:26,900 --> 00:08:29,180
In this case n is equal to six.

188
00:08:29,180 --> 00:08:32,600
So this five over here is actually n minus one.

189
00:08:32,600 --> 00:08:37,700
So if n was ten, when I is equal to zero we would do nine comparisons.

190
00:08:37,700 --> 00:08:41,990
Similarly when I is equal to one we will do four comparisons.

191
00:08:41,990 --> 00:08:45,080
When I is equal to two, we will do three comparisons.

192
00:08:45,080 --> 00:08:47,630
When I is equal to three, we will do two comparisons.

193
00:08:47,630 --> 00:08:51,200
When I is equal to four, we will do finally one comparison.

194
00:08:51,200 --> 00:08:52,130
And that ends it right.

195
00:08:52,130 --> 00:08:56,120
So we won't move to I is equal to five because then we will not have any J.

196
00:08:56,210 --> 00:09:02,030
So over here you can see that the number of operations that we are doing is actually n minus one plus

197
00:09:02,030 --> 00:09:04,310
n minus two, etc. up to one.

198
00:09:04,310 --> 00:09:06,440
So that's n minus one.

199
00:09:07,230 --> 00:09:10,950
Plus N minus two, etc. up to one.

200
00:09:10,950 --> 00:09:18,000
Now this actually sums up to n minus one into n minus one plus one by two, right?

201
00:09:18,000 --> 00:09:25,440
So this is actually n minus one into n by two which is equal to n square minus n by two.

202
00:09:25,440 --> 00:09:27,990
So the dominating factor is n square.

203
00:09:27,990 --> 00:09:32,940
That's why we can say that the time complexity of this solution is o of n square.

204
00:09:32,940 --> 00:09:39,150
Now how did I get this that n minus one plus n minus two etc. up to one that it is equal to n minus

205
00:09:39,150 --> 00:09:41,190
one into n minus one plus one by two.

206
00:09:41,220 --> 00:09:43,830
This is actually a concept from maths.

207
00:09:43,830 --> 00:09:47,520
This is because this over here is an arithmetic progression right now.

208
00:09:47,520 --> 00:09:53,490
Again, this is a good thing to know if you have the values one up to n one plus two plus three, etc.

209
00:09:53,490 --> 00:09:59,550
if you're adding it up to n this over here, you can find it as n into n plus one by two.

210
00:09:59,550 --> 00:10:05,040
So I'm just using this formula over here to find that n minus one plus n minus two, etc. up to one

211
00:10:05,040 --> 00:10:08,430
is equal to n minus one into n minus one plus one by two.

212
00:10:08,460 --> 00:10:09,000
How is that.

213
00:10:09,000 --> 00:10:12,180
So notice over here the last term is n right.

214
00:10:12,510 --> 00:10:15,810
And I'm doing n into one greater than the last term.

215
00:10:15,810 --> 00:10:18,900
So in this case the last term is n minus one.

216
00:10:18,900 --> 00:10:24,780
So I'm doing n minus one into one greater than n minus one which is n minus one plus one divided by

217
00:10:24,780 --> 00:10:24,990
two.

218
00:10:25,020 --> 00:10:26,640
So that is how we're getting this.

219
00:10:26,640 --> 00:10:29,940
And this simplifies to n square minus n by two.

220
00:10:29,940 --> 00:10:32,970
And over here the dominating factor is n square.

221
00:10:32,970 --> 00:10:36,840
That's why the time complexity of this solution is O of n square.

222
00:10:36,840 --> 00:10:37,410
All right.

223
00:10:37,410 --> 00:10:40,710
So we have seen why the time complexity is O of n square.

224
00:10:40,710 --> 00:10:42,630
What about the space complexity.

225
00:10:42,630 --> 00:10:46,410
We are not using any extra space or any auxiliary space right.

226
00:10:46,410 --> 00:10:48,810
So we are not using any extra space.

227
00:10:48,810 --> 00:10:54,240
Therefore this function or this method runs in constant space which is O of one.