1
00:00:00,880 --> 00:00:03,310
Hi everyone, let's do this question.

2
00:00:03,310 --> 00:00:07,450
You are given an integer array height of length n.

3
00:00:07,660 --> 00:00:15,550
There are n vertical lines drawn such that the two end points of the ith line are I zero and I comma

4
00:00:15,550 --> 00:00:15,970
height at.

5
00:00:15,970 --> 00:00:23,500
I find two lines that, together with the x axis, form a container such that the container contains

6
00:00:23,500 --> 00:00:27,130
the most water depth is constant across containers.

7
00:00:27,130 --> 00:00:33,790
Return the area that the two lines and the x axis make of container, which can store the maximum amount

8
00:00:33,790 --> 00:00:34,390
of water.

9
00:00:34,390 --> 00:00:36,940
Notice that you may not slant the container.

10
00:00:36,940 --> 00:00:39,130
All right, now this is the question over here.

11
00:00:39,130 --> 00:00:41,230
Now let's try to understand this question.

12
00:00:41,230 --> 00:00:43,180
And for this we will take an example.

13
00:00:43,180 --> 00:00:45,940
Let's say the array which is given which is this array right.

14
00:00:45,940 --> 00:00:47,440
The array integer array height.

15
00:00:47,440 --> 00:00:51,550
Let's say that's this one over here 1563 and four.

16
00:00:51,550 --> 00:00:52,870
Let's say this is the array.

17
00:00:52,900 --> 00:00:58,210
Now over here we can see that this actually represents n vertical lines right.

18
00:00:58,210 --> 00:00:59,380
So this is zero.

19
00:00:59,380 --> 00:01:00,640
Let me write the indices over here.

20
00:01:00,640 --> 00:01:01,360
This is zero.

21
00:01:01,360 --> 00:01:02,680
This is one this is two.

22
00:01:02,680 --> 00:01:04,960
This is three and this is four.

23
00:01:04,960 --> 00:01:10,960
Now over here we can see that the end points are I comma zero and I at height at I.

24
00:01:10,990 --> 00:01:18,640
So if we are taking this as I is zero then the end points will be zero comma zero right.

25
00:01:18,640 --> 00:01:22,600
And it would be zero comma height at zero which is one.

26
00:01:22,600 --> 00:01:25,000
So this is one line right.

27
00:01:25,000 --> 00:01:26,530
So let's just write this.

28
00:01:26,530 --> 00:01:27,490
So this is one line.

29
00:01:27,490 --> 00:01:29,050
What about this next line.

30
00:01:29,050 --> 00:01:32,140
The next line will have the indices I will be one right.

31
00:01:32,140 --> 00:01:33,850
So it will be one comma zero.

32
00:01:34,790 --> 00:01:38,150
And it will be one comma height at I which is five.

33
00:01:38,480 --> 00:01:38,750
Right.

34
00:01:38,750 --> 00:01:39,770
So one comma five.

35
00:01:39,770 --> 00:01:42,830
In this way we can draw n lines right.

36
00:01:42,830 --> 00:01:44,720
So 12345.

37
00:01:44,720 --> 00:01:46,820
The length n is five.

38
00:01:46,820 --> 00:01:50,510
So we can draw five lines five vertical lines in this manner.

39
00:01:50,510 --> 00:01:52,070
So let's go ahead and do that over here.

40
00:01:52,070 --> 00:01:55,700
Now the first line is zero comma zero and zero comma one.

41
00:01:55,700 --> 00:01:57,290
This is zero comma zero.

42
00:01:57,290 --> 00:01:59,690
Let this be the point zero comma zero.

43
00:01:59,690 --> 00:02:01,970
And this is the point zero comma one.

44
00:02:01,970 --> 00:02:04,610
Now this will be the point one comma zero.

45
00:02:04,610 --> 00:02:07,070
And this will be the point one comma five.

46
00:02:07,070 --> 00:02:07,430
Right.

47
00:02:07,430 --> 00:02:14,330
So again in the similar manner over here we have two comma zero and two comma six three comma zero and

48
00:02:14,330 --> 00:02:18,410
three comma three four comma zero and four comma four.

49
00:02:18,410 --> 00:02:22,220
So in this way is that's how we can visually see this right.

50
00:02:22,220 --> 00:02:23,750
So these are the vertical lines.

51
00:02:23,780 --> 00:02:31,220
Now the question asks us to identify two lines that together with the x axis form a container such that

52
00:02:31,220 --> 00:02:33,740
the container contains the most water.

53
00:02:33,740 --> 00:02:35,060
Now let's take an example.

54
00:02:35,060 --> 00:02:38,720
Let's say we take these two lines, this line over here and this line over here.

55
00:02:39,200 --> 00:02:40,580
Now this is the x axis.

56
00:02:40,580 --> 00:02:43,820
So what is the container over here we have this line.

57
00:02:43,820 --> 00:02:45,560
We have this line over here.

58
00:02:45,560 --> 00:02:47,390
And then we have the x axis over here.

59
00:02:47,390 --> 00:02:49,220
So this is forming a container.

60
00:02:49,220 --> 00:02:51,800
Now how much water can it contain.

61
00:02:51,800 --> 00:02:52,970
What would be the height.

62
00:02:52,970 --> 00:02:55,700
It can contain water only up to this level.

63
00:02:55,700 --> 00:02:56,030
Right.

64
00:02:56,030 --> 00:02:59,210
Because if if there is more water it will just spill out.

65
00:02:59,210 --> 00:02:59,450
Right.

66
00:02:59,450 --> 00:03:02,990
So we are forming a container where the height is one.

67
00:03:02,990 --> 00:03:05,150
And this, this that is one.

68
00:03:05,150 --> 00:03:05,870
This is one, right.

69
00:03:05,870 --> 00:03:07,730
This is one unit which is the width.

70
00:03:07,730 --> 00:03:10,730
And then the depth is constant across containers.

71
00:03:10,730 --> 00:03:11,090
Right.

72
00:03:11,180 --> 00:03:13,970
That means for example I'm forming a container over here.

73
00:03:13,970 --> 00:03:17,300
Now this container if this is six right.

74
00:03:17,300 --> 00:03:21,050
And I'm taking this line four it can take height up to four.

75
00:03:21,050 --> 00:03:21,260
Right.

76
00:03:21,260 --> 00:03:22,940
Because above four it will spill over.

77
00:03:22,940 --> 00:03:25,550
And then the width over here is two right.

78
00:03:25,550 --> 00:03:27,860
And the depth across these two is constant.

79
00:03:27,860 --> 00:03:34,580
So it does not factor into checking whether this container or this container can contain maximum water.

80
00:03:34,580 --> 00:03:39,350
Now we have to identify the container which will contain the maximum water.

81
00:03:39,350 --> 00:03:41,030
And we have to return the area.

82
00:03:41,030 --> 00:03:45,200
Now if we were to return this container over here the area would be one right.

83
00:03:45,200 --> 00:03:47,000
So one into one is one.

84
00:03:47,000 --> 00:03:52,010
Now if you are going to return this container, the area over here is four into two which is equal to

85
00:03:52,010 --> 00:03:52,490
eight.

86
00:03:52,940 --> 00:03:57,320
Now we have to identify the two lines which will form the maximum area.

87
00:03:57,320 --> 00:03:59,360
And then we have to return that area.

88
00:03:59,360 --> 00:04:00,950
So that is the question over here.

89
00:04:00,950 --> 00:04:03,140
So we have understood the question.

90
00:04:03,140 --> 00:04:08,600
Now remember in the interview when you get this question always feel free to ask clarifying questions

91
00:04:08,600 --> 00:04:11,570
so that you and the interviewer are on the same page.

92
00:04:11,570 --> 00:04:14,540
Now what could be a possible question you could ask?

93
00:04:14,540 --> 00:04:17,210
Does the y axis count as a wall?

94
00:04:17,240 --> 00:04:19,160
Now over here this is zero right.

95
00:04:19,160 --> 00:04:21,980
So the y axis is actually over here right.

96
00:04:21,980 --> 00:04:28,070
So this line over here is just drawn so that we can visualize that the length is measured across this

97
00:04:28,070 --> 00:04:28,790
dimension.

98
00:04:28,790 --> 00:04:29,000
Right.

99
00:04:29,000 --> 00:04:32,360
But the y axis will pass through zero zero.

100
00:04:32,360 --> 00:04:33,680
So this is the y axis.

101
00:04:33,680 --> 00:04:37,730
Now we could ask is the y axis to be counted as a wall.

102
00:04:37,730 --> 00:04:40,280
Because in that case I can just take this and the y axis.

103
00:04:40,280 --> 00:04:40,670
Right.

104
00:04:40,670 --> 00:04:43,310
So then that would give me the maximum area.

105
00:04:43,310 --> 00:04:47,210
Now let's say the interviewer replies no, you cannot use the y axis.

106
00:04:47,210 --> 00:04:51,800
You have to use only two of the given vertical lines which we have over here.

107
00:04:51,800 --> 00:04:52,280
All right.

108
00:04:52,280 --> 00:04:53,600
So that's clear now.

109
00:04:53,600 --> 00:04:59,570
Now another possible question that you could ask is does a line inside the container affect the area.

110
00:04:59,570 --> 00:05:00,470
What does this mean.

111
00:05:00,470 --> 00:05:06,260
For example, if you are taking this line over here which is six which has height six and this line

112
00:05:06,260 --> 00:05:10,100
over here which has height four, now over here, inside this I have a line.

113
00:05:10,100 --> 00:05:10,370
Right.

114
00:05:10,370 --> 00:05:12,890
So does this in any way affect the area.

115
00:05:12,890 --> 00:05:13,370
Right.

116
00:05:13,760 --> 00:05:16,220
So now there could be multiple cases.

117
00:05:16,220 --> 00:05:20,630
For example if you take five and three and then you have a line inside it which is greater than it,

118
00:05:20,630 --> 00:05:23,450
so does it affect it in some way.

119
00:05:23,450 --> 00:05:27,740
Or again you could have this case where you have six and four, and then you have a line which is less

120
00:05:27,740 --> 00:05:29,000
than these two inside it.

121
00:05:29,000 --> 00:05:32,360
So let's say the interviewer replies no, it does not affect it.

122
00:05:32,360 --> 00:05:32,540
Right?

123
00:05:32,540 --> 00:05:37,610
If there is a line in between the lines that you have chosen, it does not affect the area in any way.

124
00:05:37,610 --> 00:05:42,260
So we just don't need to consider this at all if we are taking these two lines.

125
00:05:42,260 --> 00:05:42,710
All right.

126
00:05:42,710 --> 00:05:43,790
So that's also clear.

127
00:05:43,790 --> 00:05:47,210
Now another possible question is what about the thickness of the lines.

128
00:05:47,210 --> 00:05:47,720
Right.

129
00:05:47,720 --> 00:05:53,630
So if this if you're drawing a very thick line you could see that the area the possible area is reducing

130
00:05:53,630 --> 00:05:54,410
right now.

131
00:05:54,410 --> 00:05:55,400
What about the thickness.

132
00:05:55,400 --> 00:05:56,360
Does it affect it.

133
00:05:56,360 --> 00:06:00,830
And let's say the interviewer replies no, don't consider the thickness of the lines.

134
00:06:00,830 --> 00:06:02,690
It should be treated as negligible.

135
00:06:02,690 --> 00:06:03,200
All right.

136
00:06:03,200 --> 00:06:05,900
So we have got a fair understanding of the question.

137
00:06:05,900 --> 00:06:08,210
And we also have understood the constraints.

138
00:06:08,210 --> 00:06:08,450
Right.

139
00:06:08,450 --> 00:06:10,850
So we know that we should not consider the y axis.

140
00:06:10,850 --> 00:06:14,090
We can only use the given lines as vertical lines.

141
00:06:14,090 --> 00:06:17,150
And the lines inside a container is not affected.

142
00:06:17,150 --> 00:06:21,560
And the thickness of the line which you are drawing is also not affecting the area.

143
00:06:21,560 --> 00:06:22,010
All right.

144
00:06:22,010 --> 00:06:23,720
So we've got a good understanding.

145
00:06:23,720 --> 00:06:26,450
Now let's go ahead and write a few test cases.

146
00:06:26,450 --> 00:06:31,610
And remember in the interview always you can ask the interviewer whether it's okay, whether both of

147
00:06:31,610 --> 00:06:33,590
you together can come up with test cases.

148
00:06:33,590 --> 00:06:34,310
So that will.

149
00:06:34,500 --> 00:06:36,390
Solidify your understanding of the question.

150
00:06:36,390 --> 00:06:42,210
And before going going ahead and solving the question, you will be very thorough with what the expected

151
00:06:42,210 --> 00:06:44,760
output or the expected function has to do.

152
00:06:44,790 --> 00:06:45,240
All right.

153
00:06:45,240 --> 00:06:47,580
Now let's go ahead and write a few test cases.

154
00:06:48,000 --> 00:06:52,500
We have already seen one test case if the given array is 15634.

155
00:06:52,530 --> 00:06:57,090
This is the, uh these are the lines that we have to that we have, we can draw.

156
00:06:57,090 --> 00:06:57,480
Right.

157
00:06:57,480 --> 00:07:02,580
And in this case, the maximum area will be obtained if you take five and four.

158
00:07:02,580 --> 00:07:02,910
Right.

159
00:07:02,910 --> 00:07:07,080
So if you take five and four we can fill the container up to this level.

160
00:07:07,080 --> 00:07:10,650
So the height will be four and the width will be 123.

161
00:07:10,650 --> 00:07:10,950
Right.

162
00:07:10,950 --> 00:07:14,850
So the area in this case will be four into three which is equal to 12.

163
00:07:14,880 --> 00:07:16,260
Now how did we find this.

164
00:07:16,260 --> 00:07:18,270
So that is what we have to do right now.

165
00:07:18,270 --> 00:07:21,330
One possibility is you can take all the possible cases right.

166
00:07:21,330 --> 00:07:24,660
So if you take one and five the area will be one into one.

167
00:07:24,660 --> 00:07:27,120
If you take one and six the area will be one into two.

168
00:07:27,150 --> 00:07:29,970
If you take one and three, the area will be one into three.

169
00:07:29,970 --> 00:07:35,070
And if you take one and four, the area will be one into four, etc. if you take all the possible cases

170
00:07:35,070 --> 00:07:40,110
and once we discuss the solution and we will discuss the brute force solution as well, you can see

171
00:07:40,110 --> 00:07:44,310
that the maximum area over here will be obtained when you take five and four.

172
00:07:44,310 --> 00:07:46,980
So in this case we get four into 123.

173
00:07:46,980 --> 00:07:47,820
This is three right.

174
00:07:47,820 --> 00:07:52,110
So this area over here will be four into three which is equal to 12.

175
00:07:52,110 --> 00:07:54,600
And that will be the maximum area in this case.

176
00:07:54,600 --> 00:07:57,300
Now let's go ahead and write another test case.

177
00:07:57,300 --> 00:08:02,550
What if the array which is given to us is ten 65657.

178
00:08:02,550 --> 00:08:04,260
Now let's visualize this.

179
00:08:04,260 --> 00:08:06,570
So over here we have ten.

180
00:08:06,570 --> 00:08:08,100
And then over here we have seven.

181
00:08:08,100 --> 00:08:11,130
And everything in between that is less than ten and seven right.

182
00:08:11,130 --> 00:08:13,230
So you have 656 and five.

183
00:08:13,230 --> 00:08:18,570
Now it's very clear that the maximum area will be obtained if we take these two lines.

184
00:08:18,570 --> 00:08:19,650
Right, ten and seven.

185
00:08:19,650 --> 00:08:23,790
Now in this case you can see that we can fill it up to a height of seven.

186
00:08:23,790 --> 00:08:27,270
And the width will be one two, three, four, five five units.

187
00:08:27,270 --> 00:08:31,470
So the area will be seven into five which is equal to 35.

188
00:08:31,470 --> 00:08:31,920
All right.

189
00:08:31,920 --> 00:08:34,680
And again over here at this point we just writing test cases.

190
00:08:34,680 --> 00:08:36,720
We're not thinking of how to solve it.

191
00:08:36,720 --> 00:08:38,490
This is the expected output.

192
00:08:38,490 --> 00:08:40,800
If the input is this array over here.

193
00:08:40,800 --> 00:08:41,430
All right.

194
00:08:41,460 --> 00:08:45,840
Now if we are getting an empty array definitely the area will be zero.

195
00:08:45,840 --> 00:08:49,500
And if you are getting an array with only one element right.

196
00:08:49,500 --> 00:08:51,180
So we cannot form a container.

197
00:08:51,180 --> 00:08:54,360
So in this case also the area is equal to zero.

198
00:08:54,360 --> 00:08:54,810
All right.

199
00:08:54,810 --> 00:08:57,240
So we have a fair understanding of the question.

200
00:08:57,240 --> 00:08:58,950
And we have written out test cases.

201
00:08:58,950 --> 00:09:02,640
And at this point the interviewer and you are at the same page.

202
00:09:02,640 --> 00:09:08,040
Now in the next video let's go ahead and think through how we can solve this question.