- 2 days ago
Transcript
00:00Next question is container with most water and this is a very important question
00:06This question can we do with ArrayList and Arrays
00:09Can you give ArrayList or Arrays?
00:13This is actually an Arrays question which I have converted in ArrayList
00:17because logic is the same
00:19Now this question has been asked for Flipkart, Dunzo name company
00:23and what are different companies changing in different companies
00:26This question will be slightly similar when you compare it with Trapping Rainwater
00:33Trapping Rainwater problem we have solved in Arrays and discussed in detail
00:37So this will be the same because the diagram is the same
00:41There is water, water and maximum water
00:46So it will be the same but their logic is slightly different
00:49How is it different? One time we will solve the question and I will explain it
00:54So let's see what is container with most water
00:56What is the question?
00:57In the question we have given N lines on the X axis
01:01I mean if my X axis is this
01:03I have given N number of lines
01:06This is my first line, this is my second line, this is my third line, this is my fourth line,
01:10this is my fifth line, this is my fourth line, this is my fifth line, this is my sixth line
01:23If I have a ninth line, this will become my fifth line, this will become a second line
01:29Or if I take this line and this one
01:32Then with these lines, the third glass will become a glass or glass like this
01:39Or I can add this line or this line to this line
01:42Now I have to use a container to make two lines
01:46which I can keep the maximum water
01:48and with this I have a height of each line
01:52I have 1, I have 1
01:56I have height here
01:56I have 8, this line is 8
01:596, it is 6
02:012, it is 2
02:035, it is 5
02:054, it is 4
02:07I have 8, it is 3
02:09and it is 7
02:10So the answer is the question
02:12If this sample is my input
02:16then the output will be like this
02:19In the output I have an answer is 49
02:21How is 49?
02:22For this particular height
02:25I have the maximum water
02:26that I can store in this line
02:29and this line
02:30and this line
02:31When I make this line and this line
02:34how much water is stored in it?
02:37If I store this container
02:39and this container
02:39I will give this width
02:40How much of this width?
02:42This index
02:44I have 1
02:45this width
02:46this width
02:46this width
02:46this width
02:46this width
02:47this width
02:47this width
02:48this width
03:07this width
03:09this width
03:09this width
03:10this width
03:10this width
03:11this width
03:13this width
03:14this width
03:15this width
03:17this width
03:18this width
03:20this width
03:21this width
03:22this width
03:23this width
03:23this width
03:23this width
03:24this width
03:24this width
03:30minus i1 which is 8 minus 1
03:33I have taken the difference between the indexes
03:37that is equal to 7
03:39so this is my width
03:39and if I want to remove maximum water in the container
03:43or I want to remove water stored in the container
03:45so I need this
03:46what I need is
03:47how much water is stored on the top
03:48or where length is stored
03:49now the water line is long
03:52the water is stored here
03:54so much water is stored
03:55because if water is stored on the top
03:58then it will spill from here
04:00then it can be stored in this container
04:03otherwise the other line is long
04:05so what is the height of the water here
04:07the height of the water is this
04:10the height of the two pillars and lines
04:13the height of the water will be the height of the container
04:16which will be equal to 7
04:18so what can I say
04:19my width is here
04:20and the height of the other is 7
04:22so the water is used in the volume
04:25I mean if I take a glass
04:27then it will be calculated
04:29but here we are calculating the area of water
04:31so this is not a little real life scenario
04:34but because in 2D
04:36it will be very easy to analyze things in coding
04:38as compared to 3D
04:40so that's why I am logically analyzing the question in 2D
04:41so this is why I am logically analyzing the question
04:42this is the answer I have already given before
04:44but now I am not discussing the answer
04:46how it came
04:47I am telling you
04:48that the answer is this
04:49that when you create a container
04:53then we will have maximum water stored
04:55how much water stored
04:57the width is equal to 7
04:59and the height of the container
05:00is equal to 7
05:02I will remove area from 7 into 7
05:03what is my water area?
05:06area will be 7 into 7
05:08which is also equal to width into height
05:10what can I say
05:11this is equal to 49
05:12so what is my output?
05:13my output turns out to be 49
05:15and I will print this 49
05:17I will print this 49
05:18so my work is
05:19that I will give x-axis
05:20n lines
05:22and I will have the height of all these lines
05:24what is I going to do?
05:26I will make a single pair
05:27which will have 2 lines
05:28and I will use both lines
05:29to make a container
05:31and I will make that container
05:32so that I will store the maximum water
05:35I will store the maximum water
05:36now there is another condition
05:38in this question
05:38that my container is not slanted
05:41slanted
05:42it means slanted
05:43I can't do this
05:44that I can imagine
05:46that my container
05:47will fill the water in this way
05:49like this
05:51it will fill the line
05:52so that I will not imagine
05:53a half container
05:54I will only imagine
05:55a rectangular container
05:56I will only imagine
05:57this is a small condition
05:58so first
05:59what do we do?
06:00first of all
06:01we will analyze the brute force approach
06:03we have studied
06:04in time complexity
06:05that to solve any question
06:07first of all
06:08look at brute force
06:09look at time complexity
06:11and then look at how
06:12how we can optimize
06:13how we can optimize
06:14how we can solve it
06:16so let's think about brute force
06:17about brute force
06:18if I said
06:19that I have
06:21n lines
06:22and I have
06:23two lines
06:24pick in these lines
06:25so I can say
06:26that I will remove all
06:27possible pairs
06:28what will I do?
06:30first of all
06:31I will pick it
06:33and then I will pick it
06:34so I have
06:36a single container
06:37this container
06:38which I do
06:40it would be
06:41first
06:41I will pick it
06:42second possible container
06:45data
06:46imagine this
06:47container
06:47how much water will be stored
06:49then I will pick it
06:51and again
06:53here I have
06:55a third container
06:56which has��
06:57so much water will be stored
07:00then I will pick main
07:01is either these pair
07:03what will happen in the position?
07:05This container will be stored in which I will store so much water
07:09What will I do? I will pick another line
07:11I picked this line
07:13What happened? My container became so big and it can store so much water
07:18What will I do? I will pick next line which is my this line
07:21Now my container will become some lines
07:24which can store so much water
07:28What will I do? I will pick this line
07:30This has another pair
07:34I have stored so much water in which I have stored so much water
07:37What will I do? I will pick it
07:41Now I have this container
07:43How much water is stored in which I will store so much water
07:47Why will I store so much water?
07:48Because the boundary of the water will decide the small line
07:52If we put water on the small line, it will spill
07:56So don't spill
07:57That's why I can store so much water in which I have stored so much water
08:01So I have seen all these possible pairs in which I have picked my first line
08:06I have picked zero-hit index
08:09Let's say that the first line is zero-hit index
08:11I have picked this line
08:13What can I do?
08:14First of all, I can make this pair
08:16So I have made these two containers
08:18In which I will store so much water in which I have stored so much water
08:21So what will I do?
08:23Second option is the same
08:25What will I do?
08:27I will store in which I can store so much water
08:30Then I will take 3rd
08:32This entire container
08:35And there I won't
08:40Know how the pairs of this
08:44get the maximum water in every pair
08:47I picked them all
08:49then I will pick them all
08:51then I will pick them all
08:52and then I will use all the indexes
08:55so I have all been here
08:55Now I have built these pairs
08:57then I have built this pair and this pair
08:59now I have built this pair
09:00and I can make pairs
09:02and once again I will make pairs
09:05what I can say?
09:07the pair I have already learned about the topic there
09:12We have talked about the pair sum. We have asked about the pair sum.
09:16We have asked about the pair sum in which we had released all possible pairs.
09:19How did they released it? It was released that we used nested loops.
09:23What do we do in the outer loop? We will choose the first one.
09:27Do I want to make a pair with it or do I want to make it with it or do
09:30I want to make it with it?
09:31What will the inner loop say?
09:32That with the next lines, you have to make a pair.
09:36How did we write the code there?
09:38We have written this code for pairs.
09:41For int i equals 0, i less than height.length.
09:46Or height because I have an array list.
09:48I can say height.size.
09:51I plus plus.
09:53I will pick the pair first.
09:56For second, I will pick another loop.
10:00J is equal to 0.
10:01J will be less than.
10:03Or J will be initialized.
10:05With i plus 1.
10:07J will be less than height.size.
10:11J plus plus.
10:13What will happen from the nested loop?
10:15Once I picked it, I picked it.
10:18Then I picked it.
10:19Then I picked it again.
10:20Then I picked it again.
10:21Then I picked it again.
10:22Then I picked it again.
10:23I will analyze all possible pairs.
10:24I will analyze all pairs.
10:25Now when I analyzed all pairs.
10:28I have analyzed all pairs.
10:29So if I want to make a pair of water stored.
10:32How do I make it?
10:33I can say my water.
10:37Which is my current pair.
10:39How much water stored?
10:40That is equal to height.
10:43How much is it?
10:44How much is it?
10:44How much is it multiplied by width?
10:45How much is it?
10:46Just like I will talk about this pair.
10:49If I picked it.
10:50Line 1 picked.
10:51And this picked it.
10:53Line 2 picked.
10:54If I picked it.
10:55Then I made a container.
10:56Then how much water stored?
10:58How much water stored?
11:01So I will store it in this way.
11:05How much water is it?
11:06How much water is it?
11:07First of all, I will remove the height of the water.
11:09I know that line 1 is of height 6.
11:13And line 2 is of height 4.
11:15Now which one is my line 2
11:18So I store the water in my container
11:19So my container will be the height of my container
11:22I will see width of 4
11:27This is the height of the water
11:29This is the distance
11:31This is equal to this index
11:32Minus this index
11:34Then there will be difference between both
11:36What is the index of 4?
11:370, 1, 2, 3, 4, 5
11:40This index is 5
11:42What is the index of line 1?
11:43What is the index of line 1?
11:452
11:46So width is equal to 3
11:48So how much water can be stored in this container?
11:5212 units
11:53So the water is stored in this container
11:55This area is equal to 12
11:57So I have removed water
11:59Now let's say I have to remove another pair
12:02Like I want to remove
12:03Now which pair is picked?
12:05I have taken this pair
12:06I have taken this pair
12:08Now I have made this pair
12:11I can say this is my line 1 and this is my line 2
12:14And this is my line 2
12:14And in their water will be stored in this way
12:17Now when the water is stored
12:18I know that the height of line 1 is equal to 8
12:21This line 2 is equal to 5
12:23This line 2 is equal to 5
12:25Now if I have to remove the height
12:27I have to remove the height
12:27Height is equal to
12:29Height is equal to
12:30Water height
12:30I have 5
12:31How much width
12:32Width is equal to
12:33Width is equal to
12:33The width is equal to
12:34The width of the index
12:34This is 5
12:35And what is the width of this 8
12:36How much difference is?
12:38It is equal to 3
12:39Because 8 is at i is equal to 1
12:41And 5 is at 2
12:433, 4
12:445 is at i is equal to 4
12:46So 4 minus 1 is equal to 3
12:47So my width will be equal to 3
12:49What I can say
12:50From here
12:51The water will be stored in this container
12:53That will be
12:5415
12:54So obviously
12:56The water is stored in this container
12:58As compared to this container
13:00So what I can say
13:01Every possible container
13:02With 2 lines
13:04I will remove the water for everyone
13:06Now who has stored the maximum water
13:08In our area
13:10It will be my largest
13:11Or most water storing container
13:13Now what I can say
13:16And I can say
13:16But I will remove the height
13:19How will the height
13:20How will it turn out?
13:21Height will be
13:22Minimum of
13:23Line 1
13:25And line 2
13:27Line 1
13:27Line 1
13:28Line 1
13:28Line 2
13:29Line 2
13:30Line 2
13:30Line 2
13:30Line 2
13:30Line 2
13:30Line 1
13:31Line 2
13:31Line 2
13:31Line 2
13:31Line 2
13:32Line 2
13:32Line 2
13:33Line 2
13:46So the minimum value will become my height
13:50What is the second parameter? I need width
13:52What will be width? I will be width
13:55I will be i minus
13:55How much width is?
13:57My first index will be minus
13:59I will be j minus i
14:02Now what will I do?
14:04I will remove their water
14:07Height multiplied by width
14:09Now I will take a global variable
14:13Maximum water
14:14I will compare it with maximum water
14:15Every time I will compare it with maximum water
14:18And I will print it with maximum
14:21This is my brute force approach
14:23We will write code for brute force
14:25Then we will optimize it
14:26What have I done?
14:28I have made a height array list
14:30Which I have stored in the same heights
14:33Now I will call a brute force approach
14:35I will call public static
14:38Void
14:38Store water
14:39In fact its return type
14:42Int
14:42It will remove maximum water
14:44The first parameter
14:48That will be
14:50Integer
14:53Height
14:54I don't think we need another parameter
14:56Then what will we do?
14:58First we define a global variable
14:59For this function
15:00To store maximum water
15:03I will initialize it with zero
15:05I will initialize it with zero
15:05Zero
15:06If I have one line in the height
15:08Then I will not make a container
15:10I will create a container
15:12It will need two boundaries
15:14That's why I will take maximum water stored
15:17Now what will I do?
15:19I will run a loop
15:19This is my brute force
15:22Brute force means to remove all pairs
15:24Then the maximum
15:25Print it
15:27So brute force will start
15:28I is equal to zero
15:29From i less than
15:30Height.size
15:32I++
15:35Then what will I do?
15:36I will try to pick first line 1
15:39Then I will pick line 2
15:41J1
15:41J less than
15:44Height.size
15:46J++
15:47Here I have picked line 2
15:49Now the first thing
15:51That I have picked up
15:52Height
15:52Height
15:53Height will be
15:54Minimum of
15:55So I am doing math.minimum
15:57Minimum of
15:59Height.get i
16:01That means
16:01The height stored in i
16:03And second
16:04This is line 1
16:05And what will my line 2
16:06Height will be
16:08Height.get j
16:10So the height stored in j
16:12That is my line 2
16:14Here I have picked up height
16:15Now width
16:17Int width
16:18Is equal to
16:19My width will be
16:21J minus i
16:21Because the difference between
16:22Both indices
16:24That will be
16:25My width
16:26Now I will pick up area
16:27So int current
16:29Water
16:30That means
16:30Current lines
16:31Current
16:32Which we are talking about
16:34Line 1, line 2
16:35How much water
16:36That will be
16:38Height into
16:39Width
16:40Now what will I do?
16:42Max water will be
16:43Math.maximum of
16:44Whatever it is
16:45Max water
16:46If the value is
16:47Maximum of
16:47It will come
16:48Not
16:49Current water
16:50If the maximum water
16:50It will come
16:52If the maximum water is
16:55Maximum of
16:56Maximum of
16:56Water
16:56And what will I do?
16:59Last
16:59I will return
17:00Max water
17:03So I have written
17:04This code
17:04It is a brute force code
17:06And you will go back
17:07And go back to your
17:08Arrays
17:08Pairs
17:10Or
17:11Calculate
17:12Pairs
17:12If you have all
17:12Pairs
17:13In any area
17:14Or in any area
17:15It will be the same code
17:17It will be the same code
17:18It will be the same code
17:18But this line will change
17:19The inside logic will be the same
17:20The outside logic will be the same
17:22Let's do it
17:22Save
17:22Now let's call
17:25Store water
17:27I will print
17:29Store water
17:30It will return
17:30Output
17:31I have the output
17:36That is equal to 49
17:37So basically
17:38I have the maximum area
17:40It has all
17:40Pairs
17:41And what is the maximum area
17:42Returned
17:4349
17:43Now I will analyze
17:45What is the brute force
17:46Time complexity
17:47Outside
17:48I have run
17:48Outer loop
17:50N times
17:51If I can see the inner loop
17:52If I can see the inner loop
17:53So every time
17:54N times
17:55First time
17:56N times
17:57Then N-1
17:58Then N-2
17:59Then N-3
18:00This way
18:01But this loop
18:02Time complexity
18:03We have already analyzed
18:04Time complexity
18:05In the chapter
18:05In the chapter
18:05We have analyzed
18:06When the outer loop
18:07From N-2
18:08The outer loop
18:09From N-2
18:09The outer loop
18:10From N-1
18:11Then we have time complexity
18:13Big of N-2
18:15So this is N-2
18:16Time complexity
18:17So if we can optimize it
18:19A little bit more
18:20Then the answer
18:21Yes
18:22From N-2
18:23Time complexity
18:23A better solution
18:26In
18:26Big of N-2
18:29That is a linear time
18:30Solution
18:30And now we will talk
18:31As we will talk
18:32As we will talk
18:32To do
18:32That is a
18:32And
18:32You