1
00:00:00,170 --> 00:00:01,430
Welcome back.

2
00:00:01,430 --> 00:00:09,560
In this video, let's try to build the intuition behind this approach for solving the Elias question,

3
00:00:09,560 --> 00:00:13,010
where we will be using the binary search as well.

4
00:00:13,400 --> 00:00:16,250
Now for this, let's take an example.

5
00:00:16,250 --> 00:00:21,890
Let's say the array which is given to us is nine, two, seven, three, four and ten.

6
00:00:21,890 --> 00:00:27,080
Now we will use a pointer to initially point at this index.

7
00:00:27,080 --> 00:00:32,870
And with this pointer we will go through all the elements in the array which is given to us.

8
00:00:32,870 --> 00:00:36,800
So initially the pointer is pointing at index zero.

9
00:00:36,800 --> 00:00:38,930
And the value over here is nine.

10
00:00:38,930 --> 00:00:45,740
Now we have to make a choice whether we can include this element in the subsequence that we are building,

11
00:00:45,740 --> 00:00:52,430
which has to be strictly increasing because as of now, we have not included any element, and because

12
00:00:52,430 --> 00:00:59,090
this is the first element in the array which is given to us, let's include this in the increasing subsequence.

13
00:00:59,630 --> 00:01:02,360
So we have added nine over here.

14
00:01:02,360 --> 00:01:04,970
And then we move this pointer ahead.

15
00:01:04,970 --> 00:01:10,280
So now the pointer is pointing at the value two because that's index one.

16
00:01:10,280 --> 00:01:12,980
Now there are two possibilities.

17
00:01:12,980 --> 00:01:17,510
One possibility is that this value over here is greater than nine.

18
00:01:17,510 --> 00:01:22,520
In which case we could just add it over here because this would still be increasing in nature.

19
00:01:22,520 --> 00:01:30,290
But over here, because two is not greater than nine, we can't directly add two over here because nine

20
00:01:30,290 --> 00:01:33,890
comma two is not an increasing subsequence.

21
00:01:33,890 --> 00:01:36,740
So what do we do in this approach?

22
00:01:36,740 --> 00:01:40,580
What we have to do is between 9 and 2.

23
00:01:40,610 --> 00:01:46,850
What do you think would be better to keep in the increasing subsequence that we are building?

24
00:01:47,060 --> 00:01:54,770
It would be logical to keep two rather than nine, because two is less than nine, and because two is

25
00:01:54,770 --> 00:01:55,520
less than nine.

26
00:01:55,520 --> 00:02:02,510
Probably if we have just two over here instead of nine, we are more likely to get elements over here

27
00:02:02,510 --> 00:02:05,780
which are greater than two compared to nine, right?

28
00:02:05,780 --> 00:02:07,370
For example, you get a three.

29
00:02:07,370 --> 00:02:09,980
If you had kept nine, you couldn't add three.

30
00:02:09,980 --> 00:02:15,110
But if you keep two over here instead of nine, you can add the three because three is greater than

31
00:02:15,110 --> 00:02:15,440
two.

32
00:02:15,470 --> 00:02:19,850
So instead of nine over here, let's replace this with a two.

33
00:02:20,690 --> 00:02:23,420
And then we proceed to the next element.

34
00:02:23,450 --> 00:02:26,510
So the next value over here is seven.

35
00:02:26,510 --> 00:02:28,670
And seven is greater than two.

36
00:02:28,700 --> 00:02:33,920
So let's add it to the subsequence that we are building which is increasing in nature.

37
00:02:34,460 --> 00:02:38,720
Let's proceed to the next element and we have the value three over here.

38
00:02:38,720 --> 00:02:42,110
And you see that three is not greater than seven.

39
00:02:42,110 --> 00:02:42,560
All right.

40
00:02:42,560 --> 00:02:47,180
So we can't add three over here because 273 is not strictly increasing.

41
00:02:47,180 --> 00:02:54,170
So we have to decide whether to keep three or whether to keep seven over here.

42
00:02:54,170 --> 00:03:00,230
Notice that between 3 and 7 it's better to keep three because three is less than seven.

43
00:03:00,230 --> 00:03:03,020
So let's replace seven with three.

44
00:03:03,020 --> 00:03:04,400
And we have three over here.

45
00:03:04,400 --> 00:03:06,650
And we move the pointer ahead.

46
00:03:07,040 --> 00:03:11,420
Now it is pointing at the value four and four is greater than three.

47
00:03:11,420 --> 00:03:13,220
So we can add it over here.

48
00:03:13,220 --> 00:03:15,530
And then again we move this forward.

49
00:03:15,530 --> 00:03:16,550
And we have ten.

50
00:03:16,550 --> 00:03:18,260
Now ten is greater than four.

51
00:03:18,260 --> 00:03:22,850
So we can add it to the subsequence that we are building which is increasing in nature.

52
00:03:22,850 --> 00:03:27,230
So we have reached the last element of the array which is given to us.

53
00:03:27,230 --> 00:03:34,820
And we have identified that the length of the longest increasing subsequence is equal to four.

54
00:03:34,850 --> 00:03:36,260
Now, always.

55
00:03:36,260 --> 00:03:43,250
This may not give you a subsequence which is part of the array which is given to us, but we will discuss

56
00:03:43,250 --> 00:03:45,710
more of that in the next video.

57
00:03:45,740 --> 00:03:52,550
Over here we have discussed the general approach to build the intuition, and the general approach that

58
00:03:52,550 --> 00:03:58,340
we will take in this approach is to iterate over all the values of the array which is given to us,

59
00:03:58,340 --> 00:04:05,780
and if an element that we are considering is greater than the last element included in the increasing

60
00:04:05,780 --> 00:04:10,730
subsequence, we will add that element as well to the increasing subsequence.

61
00:04:10,730 --> 00:04:19,910
But if that is not the case, then we will have to find the smallest element which was already included

62
00:04:19,910 --> 00:04:24,740
in the subsequence, which is greater than or equal to the new element.

63
00:04:24,740 --> 00:04:29,660
And then we replace this element over here with the new element.

64
00:04:29,660 --> 00:04:33,860
Because the new element is less than this element over here.

65
00:04:33,860 --> 00:04:38,510
Now again, in the example that we had discussed, this becomes more clear.

66
00:04:38,510 --> 00:04:44,840
So at one point we had two and seven in the subsequence and we were considering three.

67
00:04:44,840 --> 00:04:49,940
And because three is not greater than seven, we cannot add it to the subsequence.

68
00:04:49,940 --> 00:04:55,370
And in this approach we had to replace this seven over here with three.

69
00:04:55,370 --> 00:05:01,580
Now, because we were just building the intuition, I took an example over here where we did not have

70
00:05:01,580 --> 00:05:07,970
to search through this subsequence over here to identify which element had to be replaced with three.

71
00:05:07,970 --> 00:05:10,370
We will discuss that in the next video.

72
00:05:10,370 --> 00:05:17,330
But over here, remember you will see that the ideal element to be replaced is the smallest element

73
00:05:17,330 --> 00:05:18,410
which was included.

74
00:05:18,410 --> 00:05:20,420
That's greater than the three over here.

75
00:05:20,420 --> 00:05:29,000
So for example, if we had two, four and seven and let's say we were considering whether we can include

76
00:05:29,000 --> 00:05:34,880
the element three or not, now the smallest included element which is greater than three in this case

77
00:05:34,880 --> 00:05:35,900
would be four.

78
00:05:35,900 --> 00:05:39,410
And we would have to replace this element over here with three.

79
00:05:39,410 --> 00:05:41,480
But more of that in the next video.