1
00:00:00,630 --> 00:00:01,710
Welcome back.

2
00:00:01,710 --> 00:00:06,270
Let's now take this sample input three, seven, five, six, eight and four.

3
00:00:06,270 --> 00:00:07,650
Let me just write that over here.

4
00:00:07,650 --> 00:00:15,150
Three, 7568 and four and walk through the code that we have just now written the brute force solution

5
00:00:15,150 --> 00:00:16,950
to find the maximum area.

6
00:00:16,950 --> 00:00:18,270
So this is the array.

7
00:00:18,270 --> 00:00:18,750
All right.

8
00:00:18,750 --> 00:00:21,570
And let's also write the indices over here.

9
00:00:21,570 --> 00:00:22,440
This is zero.

10
00:00:22,470 --> 00:00:24,960
This is one this is two this is three.

11
00:00:24,960 --> 00:00:27,120
This is four and this is five.

12
00:00:27,120 --> 00:00:27,630
All right.

13
00:00:27,660 --> 00:00:31,140
Now initially area is equal to zero and I is over here.

14
00:00:31,140 --> 00:00:33,240
This is where I is I is at zero.

15
00:00:33,240 --> 00:00:36,690
And then we have J over here at I plus one which is over here.

16
00:00:36,690 --> 00:00:42,000
Right now we are going to find the height which is the minimum among these two, which is what we do

17
00:00:42,000 --> 00:00:42,360
over here.

18
00:00:42,360 --> 00:00:42,690
Right.

19
00:00:42,690 --> 00:00:45,150
So the minimum at this point is three.

20
00:00:45,150 --> 00:00:50,310
And the width at this point is j minus I which is one -0 which is one.

21
00:00:50,310 --> 00:00:53,550
So we get the area as three into one which is three.

22
00:00:53,550 --> 00:00:56,190
And then the area at this point is zero.

23
00:00:56,190 --> 00:01:01,530
So we are going to assign to area the maximum among zero and three which is equal to three right.

24
00:01:01,530 --> 00:01:03,210
So this becomes three.

25
00:01:03,210 --> 00:01:07,440
And then we are again incrementing I incrementing j right.

26
00:01:07,440 --> 00:01:09,510
So j goes from here to here.

27
00:01:10,520 --> 00:01:16,160
Now we are going to check the minimum among these two, which is again three, and we are going to multiply

28
00:01:16,160 --> 00:01:18,980
it with the width which is two -0, which is two.

29
00:01:18,980 --> 00:01:19,280
Right.

30
00:01:19,280 --> 00:01:20,930
So we are getting six over here.

31
00:01:20,930 --> 00:01:27,050
And then over here we are going to update the area to the maximum value among three and six which is

32
00:01:27,050 --> 00:01:27,440
six.

33
00:01:27,440 --> 00:01:27,710
Right.

34
00:01:27,710 --> 00:01:29,120
So this becomes six over here.

35
00:01:29,120 --> 00:01:31,640
And in this way we are going to continue with J.

36
00:01:31,640 --> 00:01:35,120
Again we come over here and the minimum among these two is three.

37
00:01:35,120 --> 00:01:38,210
And then the width over here is three -0 which is three.

38
00:01:38,210 --> 00:01:39,560
So the area is nine.

39
00:01:39,560 --> 00:01:43,580
So this gets updated to nine at this point over here again we move J.

40
00:01:43,580 --> 00:01:44,480
We come over here.

41
00:01:44,480 --> 00:01:50,480
Now the minimum among three and eight which is three and four -0 is equal to four.

42
00:01:50,480 --> 00:01:52,400
So the area gets updated to 12.

43
00:01:52,400 --> 00:01:53,600
Three into four is 12.

44
00:01:53,600 --> 00:01:54,920
Again we come over here.

45
00:01:54,920 --> 00:02:00,260
The minimum among three and four is three and the width is five -0 right.

46
00:02:00,260 --> 00:02:02,060
So which is equal to five.

47
00:02:02,060 --> 00:02:05,120
Now again the area gets updated to 15.

48
00:02:05,120 --> 00:02:07,610
Now we are done with one round right.

49
00:02:07,610 --> 00:02:15,170
So I was zero now and J has reached over here which is index five which is less than array dot length.

50
00:02:15,170 --> 00:02:16,160
Array dot length is six.

51
00:02:16,160 --> 00:02:16,490
Right.

52
00:02:16,490 --> 00:02:18,980
So j no longer can go further.

53
00:02:18,980 --> 00:02:22,190
And at this point we are going to change I right.

54
00:02:22,190 --> 00:02:23,420
So I comes over here.

55
00:02:23,420 --> 00:02:25,070
This is where I is at this point.

56
00:02:25,070 --> 00:02:28,040
And we are going to increment through these values for J.

57
00:02:28,040 --> 00:02:29,240
And we are going to continue.

58
00:02:29,240 --> 00:02:31,970
So this is how the solution works over here.

59
00:02:31,970 --> 00:02:39,200
And when we get I over here and once we get to J to this value which is eight, we will see that the

60
00:02:39,200 --> 00:02:43,670
area is seven into four minus one which is three which gives us 21.

61
00:02:43,670 --> 00:02:46,190
And that's the max area for this solution.

62
00:02:46,190 --> 00:02:49,460
Now what about the time and space complexity for this solution?

63
00:02:49,460 --> 00:02:51,350
Let's just make some space over here.

64
00:02:52,490 --> 00:02:55,370
So it's pretty straightforward how this function works.

65
00:02:55,400 --> 00:02:58,730
Now let's look at the time and space complexity again.

66
00:02:58,760 --> 00:03:02,390
Now the time complexity for this solution is O of n square.

67
00:03:02,390 --> 00:03:04,730
And the space complexity is O of one.

68
00:03:04,730 --> 00:03:08,150
Now why the space complexity is O of one is pretty straightforward, right?

69
00:03:08,150 --> 00:03:11,540
We're not using any extra space or any auxiliary space.

70
00:03:11,540 --> 00:03:17,450
So the space complexity is O of one and the time complexity is O of n square because we have nested

71
00:03:17,450 --> 00:03:18,410
for loops over here.

72
00:03:18,410 --> 00:03:18,800
Right.

73
00:03:18,800 --> 00:03:22,490
So I is going to go in this case let's just take this example.

74
00:03:22,490 --> 00:03:25,970
Over here is 0123, four and five.

75
00:03:25,970 --> 00:03:26,330
Right.

76
00:03:26,330 --> 00:03:29,300
So I will go from 0 to 4.

77
00:03:29,300 --> 00:03:29,780
Right.

78
00:03:29,780 --> 00:03:31,190
And this is five right.

79
00:03:31,190 --> 00:03:32,870
So I will go from 0 to 4.

80
00:03:32,870 --> 00:03:40,040
When I is equal to zero J is going to take the values of 7 to 4 right which is one, two, three, four

81
00:03:40,040 --> 00:03:40,670
and five.

82
00:03:40,670 --> 00:03:43,970
So we're going to do five operations when I is equal to zero.

83
00:03:43,970 --> 00:03:47,900
And I'm having one over here, two over here, three over here and four right.

84
00:03:47,900 --> 00:03:49,880
Because I will go from 0 to 4.

85
00:03:49,880 --> 00:03:56,570
Now let's take the worst case in this case J will go five values seven, five, six, eight and four.

86
00:03:56,600 --> 00:03:57,770
That's five operations.

87
00:03:57,770 --> 00:04:03,290
Now when I is equal to one that's I is over here J will go over these values which is four.

88
00:04:03,290 --> 00:04:03,650
Right.

89
00:04:03,650 --> 00:04:05,330
Similarly over here there will be three.

90
00:04:05,330 --> 00:04:09,410
That is when I is over here there will J will take these three positions right.

91
00:04:09,410 --> 00:04:10,370
These three values.

92
00:04:10,370 --> 00:04:11,570
Similarly over here you have one.

93
00:04:11,570 --> 00:04:13,160
And then you have one operation over here.

94
00:04:13,160 --> 00:04:17,660
So the total number of operations you can see is five plus four plus three plus two plus one.

95
00:04:17,660 --> 00:04:19,070
This five over here right.

96
00:04:19,070 --> 00:04:20,300
This is n minus one.

97
00:04:20,300 --> 00:04:21,800
Right n over here is six.

98
00:04:22,010 --> 00:04:22,940
This is n minus one.

99
00:04:22,940 --> 00:04:25,190
This is n minus two etc. up to one.

100
00:04:25,190 --> 00:04:27,050
Now if you add these up right.

101
00:04:27,050 --> 00:04:31,250
If you do n minus one plus n minus two up to one.

102
00:04:31,250 --> 00:04:31,610
Right.

103
00:04:31,610 --> 00:04:36,080
So this over here sums up to n minus one.

104
00:04:36,810 --> 00:04:41,640
Into n minus one plus one divided by two.

105
00:04:41,640 --> 00:04:42,090
Right.

106
00:04:42,090 --> 00:04:47,040
So this over here, if you simplify it you will have a term with n square right.

107
00:04:47,040 --> 00:04:51,690
If you just simplify this is nothing but n minus one into n divided by two.

108
00:04:51,720 --> 00:04:55,380
Now if you simplify this you get n square minus n by two.

109
00:04:55,410 --> 00:04:59,400
So this over here has the dominating factor of n square.

110
00:04:59,400 --> 00:05:03,870
That's why we can say that the time complexity of this solution is O of n square.

111
00:05:03,870 --> 00:05:08,100
So this is one way the mathematical way at looking at it or over here.

112
00:05:08,100 --> 00:05:10,650
Also you can see that we have two for loops right.

113
00:05:10,650 --> 00:05:14,790
So for every I again we are doing almost n operations over here.

114
00:05:14,790 --> 00:05:15,090
Right.

115
00:05:15,090 --> 00:05:19,110
So and then I also takes this almost n operations.

116
00:05:19,110 --> 00:05:23,850
So that is also the intuitive way in which you can understand that the time complexity of this solution

117
00:05:23,850 --> 00:05:25,620
is O of n square.