1 00:00:00,640 --> 00:00:01,720 Welcome back. 2 00:00:01,720 --> 00:00:05,440 Now over here we have the code which we just now wrote. 3 00:00:05,470 --> 00:00:12,160 Now let's walk through it and let's take the input as 375684. 4 00:00:12,310 --> 00:00:12,820 Right. 5 00:00:14,060 --> 00:00:16,100 So this is the array which is given to us. 6 00:00:16,100 --> 00:00:21,560 Let me write the indices over here zero, one, two, three, four and five. 7 00:00:21,770 --> 00:00:22,100 All right. 8 00:00:22,100 --> 00:00:23,300 So that's the input. 9 00:00:23,300 --> 00:00:24,830 Now let's walk through the code. 10 00:00:24,830 --> 00:00:25,970 What is happening over here. 11 00:00:25,970 --> 00:00:29,390 First area is set to zero and we have two pointers. 12 00:00:29,390 --> 00:00:30,710 Right eye is set to zero. 13 00:00:30,710 --> 00:00:31,880 So I is over here. 14 00:00:31,880 --> 00:00:35,810 And J is set to array dot length minus one which is over here. 15 00:00:35,960 --> 00:00:38,150 The length is six six minus one is five. 16 00:00:38,150 --> 00:00:39,290 So J is set over here. 17 00:00:39,290 --> 00:00:43,910 Now as long as I is less than j we are going to loop right. 18 00:00:43,910 --> 00:00:45,350 So that's the while loop over here. 19 00:00:45,350 --> 00:00:49,550 Now we are going to check the minimum value among these two three and four. 20 00:00:49,580 --> 00:00:50,930 The minimum is three right. 21 00:00:50,930 --> 00:00:57,980 So we are going to find the new area which is three into J minus I which is five -0 which is five. 22 00:00:57,980 --> 00:01:01,040 So the new area at this point is 15. 23 00:01:01,040 --> 00:01:03,170 And then over here the area was zero. 24 00:01:03,170 --> 00:01:09,260 So we are going to take the maximum value among zero and 15 to be area which is equal to 15. 25 00:01:09,260 --> 00:01:11,420 So this is changing to 15. 26 00:01:11,420 --> 00:01:14,780 And then we are going to check whether which among these two is lesser. 27 00:01:14,780 --> 00:01:17,780 So we see that r I at I is less than array at j. 28 00:01:17,780 --> 00:01:21,050 So therefore we are going to change the I pointer. 29 00:01:21,050 --> 00:01:22,250 So we are going to increment it. 30 00:01:22,250 --> 00:01:23,510 And I comes over here. 31 00:01:23,510 --> 00:01:25,520 Now again I is less than J. 32 00:01:25,520 --> 00:01:27,410 So again we loop through over here. 33 00:01:27,410 --> 00:01:31,370 Now we are going to find the minimum among seven and four which is four right. 34 00:01:31,370 --> 00:01:32,630 So we have four. 35 00:01:32,630 --> 00:01:36,740 And then the difference between the pointers five and one is four. 36 00:01:36,740 --> 00:01:38,300 So four into four is 16. 37 00:01:38,300 --> 00:01:41,120 So we're going to change the array the area to 16. 38 00:01:41,120 --> 00:01:42,470 So let me just write that over here. 39 00:01:42,470 --> 00:01:44,060 We have area as 16. 40 00:01:44,060 --> 00:01:48,980 And again we are going to check whether this is less than this which is not the case. 41 00:01:48,980 --> 00:01:50,780 So we're going to change the j pointer. 42 00:01:50,780 --> 00:01:52,130 So j minus minus. 43 00:01:52,130 --> 00:01:53,900 So J comes over here right. 44 00:01:53,900 --> 00:01:55,070 So J is over here. 45 00:01:55,370 --> 00:01:58,070 Now again I is still less than J. 46 00:01:58,070 --> 00:02:00,410 So I is over here at one and J is at four. 47 00:02:00,410 --> 00:02:01,580 So I is less than J. 48 00:02:01,580 --> 00:02:03,470 So we again loop through over here. 49 00:02:03,590 --> 00:02:07,100 We are going to find the minimum between 7 and 8 which is seven. 50 00:02:07,770 --> 00:02:13,380 And we're going to multiply this with j minus I which is four minus one which is three. 51 00:02:13,410 --> 00:02:15,570 So seven into three gives us 21. 52 00:02:15,570 --> 00:02:17,190 And that is greater than 16. 53 00:02:17,190 --> 00:02:21,090 So we are going to change the value of area to 21 at this point. 54 00:02:21,090 --> 00:02:21,450 Right. 55 00:02:21,450 --> 00:02:24,750 The maximum of 16 and 21 which is 21. 56 00:02:24,750 --> 00:02:27,720 Again we are going to check whether seven is less than eight. 57 00:02:27,720 --> 00:02:28,710 Yes that's true. 58 00:02:28,710 --> 00:02:32,070 Therefore we are going to change this pointer by doing I plus plus. 59 00:02:32,070 --> 00:02:34,950 So I is pointing to this second index over here. 60 00:02:34,950 --> 00:02:37,620 At this point now I is still less than J. 61 00:02:37,620 --> 00:02:38,100 All right. 62 00:02:38,100 --> 00:02:42,300 So we are going to take the minimum among five and eight which is five. 63 00:02:42,300 --> 00:02:45,540 And we will multiply this with four minus two which is two. 64 00:02:45,570 --> 00:02:47,040 So five into two is ten. 65 00:02:47,040 --> 00:02:50,550 And among 21 and 1021 is the greater value. 66 00:02:50,550 --> 00:02:52,110 So we don't change the area. 67 00:02:52,110 --> 00:02:56,100 Now among five and eight we can see that five is less right. 68 00:02:56,100 --> 00:02:58,530 So our at I is less than area j. 69 00:02:58,530 --> 00:02:59,970 So we do I plus plus. 70 00:02:59,970 --> 00:03:01,380 So I comes over here. 71 00:03:02,340 --> 00:03:04,290 Now we are going to check again. 72 00:03:04,290 --> 00:03:09,120 We are going to loop through again because I is less than J now among six and eight the minimum value 73 00:03:09,120 --> 00:03:10,050 is six, right. 74 00:03:10,050 --> 00:03:13,560 And then we are going to multiply it with four minus three which is one. 75 00:03:13,560 --> 00:03:15,870 So six into one just is equal to six. 76 00:03:15,870 --> 00:03:18,600 Now among 21 and 621 is greater. 77 00:03:18,600 --> 00:03:22,140 So we don't change the area now among six and eight. 78 00:03:22,140 --> 00:03:25,050 Yes you can see that six is less than eight. 79 00:03:25,050 --> 00:03:26,310 So we do I plus plus. 80 00:03:26,310 --> 00:03:28,200 So I comes over here right. 81 00:03:28,200 --> 00:03:29,250 So I comes over here. 82 00:03:29,250 --> 00:03:32,280 So I and J both are pointing at index four. 83 00:03:32,280 --> 00:03:35,880 Now when we check over here I is not less than J right. 84 00:03:35,880 --> 00:03:37,230 Four is not less than four. 85 00:03:37,230 --> 00:03:41,730 So we come out of it and we are just going to return the area which is 21. 86 00:03:41,730 --> 00:03:44,730 So this is how the function works which we have written. 87 00:03:44,730 --> 00:03:50,790 Now we can see that we have done a lot less number of operations than the brute force solution. 88 00:03:50,790 --> 00:03:51,120 Right. 89 00:03:51,120 --> 00:03:54,390 So let's look at the time and space complexity of the solution. 90 00:03:54,390 --> 00:03:59,850 Now the time complexity over here is O of N and the space complexity is O of one. 91 00:03:59,850 --> 00:04:05,460 Now we can see that we went through the given array 375684. 92 00:04:05,490 --> 00:04:06,540 That was the array, right? 93 00:04:06,540 --> 00:04:08,220 We went through it only once. 94 00:04:08,220 --> 00:04:10,410 We are touching every element only once, right. 95 00:04:10,410 --> 00:04:13,500 So we can see that the time complexity is O of n. 96 00:04:13,500 --> 00:04:16,080 Now if we look at the number of operations right. 97 00:04:16,080 --> 00:04:18,750 So let's just quickly look at that as well. 98 00:04:18,750 --> 00:04:22,800 We can see that we are doing only n by two operations. 99 00:04:22,800 --> 00:04:26,430 So initially I is over here and J is over here. 100 00:04:26,430 --> 00:04:28,470 So we are going to compare these two values. 101 00:04:28,470 --> 00:04:34,590 Right now let's say we are always moving I now again we will only move the value which is minimum among 102 00:04:34,590 --> 00:04:34,980 the two. 103 00:04:35,010 --> 00:04:38,190 But always at every step we will move one of the pointers right. 104 00:04:38,190 --> 00:04:41,220 So when it comes to the number of operations it does not matter. 105 00:04:41,220 --> 00:04:42,870 So just to get a feeling. 106 00:04:42,870 --> 00:04:44,910 So over here we have done one operation. 107 00:04:44,910 --> 00:04:47,130 Now let's say we move the pointer again. 108 00:04:47,130 --> 00:04:48,180 We do one operation. 109 00:04:48,180 --> 00:04:50,070 We again move the pointer again. 110 00:04:50,070 --> 00:04:52,110 We do one operation again we do. 111 00:04:52,140 --> 00:04:56,490 We move the pointer, we do one more operation and we move the the pointer again. 112 00:04:56,490 --> 00:04:57,720 And we do one more operation. 113 00:04:57,720 --> 00:05:03,840 So you can see that if we have six elements over here, we are going to do five operations, which is 114 00:05:03,840 --> 00:05:05,490 o n minus one operations. 115 00:05:05,490 --> 00:05:07,290 And that is of the order of n. 116 00:05:07,290 --> 00:05:13,050 So that's why we can say that we are doing N operations or the time complexity over here is O of n. 117 00:05:13,050 --> 00:05:14,730 And again I'm just repeating it over here. 118 00:05:14,730 --> 00:05:20,520 We will not always move the I pointer the pointer which is pointing at the value which is lower right. 119 00:05:20,520 --> 00:05:22,350 Only that pointer will be moved right. 120 00:05:22,350 --> 00:05:26,250 But again, whichever pointer is moved we will move that pointer. 121 00:05:26,250 --> 00:05:33,450 And then there will be an operation which is finding the height which is minimum of minimum value when 122 00:05:33,450 --> 00:05:37,500 among the two values right where the two pointers are pointing. 123 00:05:37,500 --> 00:05:39,330 So we will take the minimum as the height. 124 00:05:39,330 --> 00:05:42,900 And then we go ahead and do some constant time operations over here. 125 00:05:42,900 --> 00:05:48,510 So we have seen that the time complexity over here is of the order of N, and the space complexity is 126 00:05:48,510 --> 00:05:51,600 O of one, because we are not using any auxiliary space.