1
00:00:00,260 --> 00:00:02,390
Hey there and welcome back!

2
00:00:02,420 --> 00:00:09,800
In the previous video, we have started to develop the intuition behind this approach for solving the

3
00:00:09,800 --> 00:00:12,140
Liz question over here.

4
00:00:12,170 --> 00:00:16,160
Let's start with thinking about two aspects.

5
00:00:17,010 --> 00:00:20,610
First of all, let's try to think why this works.

6
00:00:20,850 --> 00:00:28,470
This part over here where if we encounter an element which is not greater than the last included element,

7
00:00:28,470 --> 00:00:35,490
why does replacing the smallest included element greater than the new element actually work?

8
00:00:35,520 --> 00:00:37,380
So let's discuss this aspect.

9
00:00:37,410 --> 00:00:45,480
Secondly, let's also discuss why in this approach, after we are done iterating through all the elements

10
00:00:45,480 --> 00:00:53,460
in the array which is given to us, we may not get an actual increasing subsequence which is part of

11
00:00:53,460 --> 00:00:56,250
this array, but we will still get the length.

12
00:00:56,250 --> 00:01:03,180
And remember, the question only asks us to identify the length of the longest increasing subsequence.

13
00:01:03,420 --> 00:01:09,480
So let's get started and discuss these two aspects of this approach.

14
00:01:10,070 --> 00:01:12,590
So let's take another example over here.

15
00:01:12,590 --> 00:01:17,180
Let's say the array which is given to me is two, three, four and one.

16
00:01:17,210 --> 00:01:20,450
Now let's walk through the approach that we have discussed over here.

17
00:01:20,450 --> 00:01:25,340
So initially we have two we included in the subsequence that we are building.

18
00:01:25,340 --> 00:01:28,160
Now we move to the next element which is three.

19
00:01:28,160 --> 00:01:29,900
Now three is greater than two.

20
00:01:29,930 --> 00:01:31,880
So let's include it over here.

21
00:01:31,880 --> 00:01:33,560
We move to the next element.

22
00:01:33,560 --> 00:01:34,550
We get four.

23
00:01:34,550 --> 00:01:36,140
Now four is greater than three.

24
00:01:36,140 --> 00:01:37,910
So we include it over here.

25
00:01:37,910 --> 00:01:39,410
Then we move to one.

26
00:01:39,410 --> 00:01:41,630
Now one is not greater than four.

27
00:01:41,630 --> 00:01:48,110
So we have to identify the smallest included element which is greater than equal to one.

28
00:01:48,110 --> 00:01:54,980
So the smallest included element or the smallest value among these three values which is greater than

29
00:01:54,980 --> 00:01:56,780
or equal to one is two.

30
00:01:56,780 --> 00:01:59,570
And we replace two with one.

31
00:01:59,570 --> 00:02:07,490
So notice that over here the increasing subsequence that we are getting is one, three, four, which

32
00:02:07,490 --> 00:02:12,050
is not a subsequence of the array which is given to us.

33
00:02:12,050 --> 00:02:12,530
Right.

34
00:02:12,530 --> 00:02:15,320
So that's what I meant with point number two over here.

35
00:02:15,320 --> 00:02:22,430
But that does not matter, because the length of this is still the length of the longest increasing

36
00:02:22,430 --> 00:02:25,670
subsequence in the array which is given to us.

37
00:02:25,670 --> 00:02:27,740
And that's all that we are asked to find.

38
00:02:27,740 --> 00:02:31,310
So the length of the longest increasing subsequence over here is three.

39
00:02:31,310 --> 00:02:36,200
And over here also notice that the length of the longest increasing subsequence is three.

40
00:02:36,200 --> 00:02:40,490
So this approach actually works and helps us identify the length.

41
00:02:40,490 --> 00:02:43,970
But then let's discuss more about the why now.

42
00:02:43,970 --> 00:02:46,910
So why does this approach work now?

43
00:02:46,910 --> 00:02:50,810
To discuss this aspect, let me take two examples.

44
00:02:50,810 --> 00:02:57,860
So let's say the array which is given to us in example one is 910 and one.

45
00:02:57,860 --> 00:03:03,740
And let's say in example two, the array which is given to us is nine, ten, one, two and three.

46
00:03:03,890 --> 00:03:10,760
Now in the case of the first example, we would first add nine to the subsequence array that we are

47
00:03:10,760 --> 00:03:12,590
building which is increasing in nature.

48
00:03:12,590 --> 00:03:14,690
Then we come to the next element.

49
00:03:14,690 --> 00:03:17,870
As ten is greater than nine, we can include it over here.

50
00:03:18,260 --> 00:03:21,620
And then we come to the next element which is equal to one.

51
00:03:21,620 --> 00:03:25,850
Now one is not greater than ten, so we can't place it over here.

52
00:03:25,850 --> 00:03:31,850
And then we have to find the smallest included element which is greater than or equal to one.

53
00:03:31,850 --> 00:03:37,580
And among nine and ten, the smallest included element greater than or equal to one is nine.

54
00:03:37,580 --> 00:03:40,130
So we replace nine with one.

55
00:03:40,280 --> 00:03:49,190
Now first of all, notice that we still do get the length of the longest increasing subsequence, because

56
00:03:49,190 --> 00:03:53,180
when we included one over here, the length did not change.

57
00:03:53,180 --> 00:04:00,500
When we just had nine and ten, the length of this subsequence was equal to two, and even after changing

58
00:04:00,500 --> 00:04:03,890
9 to 1, the length over here is still two.

59
00:04:03,920 --> 00:04:12,020
So the length of the subsequence that we are building only changes when we encounter an element which

60
00:04:12,020 --> 00:04:15,140
is larger than the last included element.

61
00:04:15,140 --> 00:04:17,030
So that's why this works.

62
00:04:17,030 --> 00:04:20,630
And over here we still get the answer which is two.

63
00:04:20,660 --> 00:04:21,980
That's the length over here.

64
00:04:21,980 --> 00:04:26,000
And that is the length of the longest increasing subsequence over here.

65
00:04:26,090 --> 00:04:31,940
Even though one comma ten is not a subsequence of this array over here.

66
00:04:32,450 --> 00:04:35,450
Now let's take a look at the second example over here.

67
00:04:35,450 --> 00:04:37,310
And let's build the solution.

68
00:04:37,310 --> 00:04:39,560
So we start by including nine.

69
00:04:39,920 --> 00:04:42,650
Then we proceed to the next element which is ten.

70
00:04:42,650 --> 00:04:44,870
Ten is greater than this nine over here.

71
00:04:44,870 --> 00:04:46,580
So we can include it.

72
00:04:47,200 --> 00:04:48,580
And then we come to one.

73
00:04:48,580 --> 00:04:50,350
Now one is not greater than ten.

74
00:04:50,350 --> 00:04:54,610
So we replace and change this nine over here to one.

75
00:04:55,420 --> 00:04:57,820
And then we come to the next element, which is two.

76
00:04:57,820 --> 00:05:00,700
Now two is also not greater than ten.

77
00:05:00,700 --> 00:05:06,940
So we have to identify the smallest included element which is greater than or equal to two.

78
00:05:06,970 --> 00:05:13,390
So in this case that's going to be equal to ten because one is not greater than or equal to two.

79
00:05:13,420 --> 00:05:18,760
So the smallest included element greater than or equal to two is this ten over here.

80
00:05:18,760 --> 00:05:21,400
So we replace ten with two.

81
00:05:21,400 --> 00:05:24,790
And now the subsequence over here is one comma two.

82
00:05:24,790 --> 00:05:26,650
And then we come to the next element.

83
00:05:26,650 --> 00:05:28,300
And three is greater than two.

84
00:05:28,330 --> 00:05:30,280
So we can include it over here.

85
00:05:30,280 --> 00:05:34,780
And notice that we get a subsequence over here of length three.

86
00:05:34,810 --> 00:05:39,790
Now why was it needed to replace this nine over here with one?

87
00:05:39,790 --> 00:05:46,570
Notice that to capture this subsequence, which is a possibility, we had to do this.

88
00:05:46,570 --> 00:05:52,720
So even though doing this, if it was just over here, if the question was just this much, doing this

89
00:05:52,720 --> 00:05:58,990
change did not change the length of the list, which in a way meant that it did not harm the solution,

90
00:05:58,990 --> 00:06:05,080
but it was still necessary for the solution to capture this possibility over here.

91
00:06:05,080 --> 00:06:08,110
So this is why this approach works.

92
00:06:08,680 --> 00:06:11,500
Now let's quickly summarize what we have learned.

93
00:06:11,500 --> 00:06:13,930
So let's say this is the array which is given to us.

94
00:06:13,930 --> 00:06:20,920
So we build a subsequence by iterating over the elements in the array which is given to us.

95
00:06:20,920 --> 00:06:28,600
And if we find an element which is larger than the last included element, we will append it or include

96
00:06:28,600 --> 00:06:29,860
it to the subsequence.

97
00:06:29,860 --> 00:06:38,050
And if that is not the case, then we will replace the smallest element which is greater than or equal

98
00:06:38,050 --> 00:06:42,640
to the new element which was already included in the subsequence.

99
00:06:42,640 --> 00:06:45,340
So this is the approach that we will take over here.

100
00:06:45,340 --> 00:06:49,870
Now where does binary search come into play in this approach.

101
00:06:49,870 --> 00:06:58,630
So it's going to come into play over here because we have to identify in the subsequence which is the

102
00:06:58,630 --> 00:07:04,960
smallest element greater than or equal to the new element which is already included in the subsequence.

103
00:07:04,960 --> 00:07:12,190
Now for this or to identify this element, we could do normal search which is going to be an O of n

104
00:07:12,190 --> 00:07:12,970
operation.

105
00:07:12,970 --> 00:07:18,940
Or we could do binary search, which is going to be an O of log n operation.

106
00:07:18,940 --> 00:07:25,480
And because we have to do this for all elements, if we implement the normal search, the total time

107
00:07:25,480 --> 00:07:28,000
complexity is going to be n into n.

108
00:07:28,000 --> 00:07:35,530
But by implementing binary search, the total time complexity is just going to be n into log n.