1
00:00:00,110 --> 00:00:01,910
Hey there and welcome back.

2
00:00:01,910 --> 00:00:08,030
So in the previous videos we have discussed the list type dynamic programming questions.

3
00:00:08,030 --> 00:00:12,560
Now over here let's do another question which is of the same type.

4
00:00:12,560 --> 00:00:15,320
So let's go ahead and read the question.

5
00:00:15,320 --> 00:00:19,850
And let's also discuss why this is an alias type question.

6
00:00:19,850 --> 00:00:21,140
So let's get started.

7
00:00:21,140 --> 00:00:25,730
The question is the maximum length of pair chain question.

8
00:00:25,730 --> 00:00:35,930
The question reads you are given an array of n pairs where pairs I is equal to left I and right I.

9
00:00:35,960 --> 00:00:41,960
So again it just says that each pair has two elements and left less than right.

10
00:00:41,960 --> 00:00:50,120
So in each pair the value at the left position will be lower than the value at the right position.

11
00:00:50,330 --> 00:01:00,110
A pair p two is equal to c comma d follows a pair p one, which is a comma b if b less than c.

12
00:01:00,110 --> 00:01:02,150
So again what does this say over here.

13
00:01:02,150 --> 00:01:06,560
So let's say you have two pairs a comma b and c comma d.

14
00:01:06,950 --> 00:01:14,150
And if b is less than c then this pair over here follows this pair okay.

15
00:01:14,150 --> 00:01:18,170
And these together make up a chain of pairs.

16
00:01:18,170 --> 00:01:24,050
So it says over here a chain of pairs can be formed in this fashion.

17
00:01:24,170 --> 00:01:29,750
Return the length of the longest chain which can be formed.

18
00:01:29,750 --> 00:01:30,860
So that's the question.

19
00:01:30,860 --> 00:01:35,150
We have to find the longest chain that can be formed.

20
00:01:35,150 --> 00:01:38,300
And again the definition of a chain is given over here.

21
00:01:38,300 --> 00:01:44,390
And we have to finally return the length of that particular chain, which is the longest chain that

22
00:01:44,390 --> 00:01:45,380
can be formed.

23
00:01:45,380 --> 00:01:49,280
You do not need to use up all the given intervals.

24
00:01:49,280 --> 00:01:52,130
You can select pairs in any order.

25
00:01:52,130 --> 00:01:53,360
So that's the question.

26
00:01:53,360 --> 00:01:55,490
And we are given an example over here.

27
00:01:55,490 --> 00:01:58,970
If the pairs array is this array over here.

28
00:01:58,970 --> 00:02:00,950
And notice we have three pairs.

29
00:02:00,950 --> 00:02:06,410
Now if this is the input array then the required output is equal to two.

30
00:02:06,410 --> 00:02:11,630
Because we can only form a chain of pairs involving two elements.

31
00:02:11,630 --> 00:02:15,890
So we have one comma two over here and four comma five over here.

32
00:02:15,890 --> 00:02:19,760
And this is a valid pair because two is less than four.

33
00:02:19,760 --> 00:02:22,220
And that's the condition which is given over here okay.

34
00:02:22,220 --> 00:02:28,700
So in the question it's mentioned that we have to find the longest chain possible.

35
00:02:28,700 --> 00:02:31,490
And we can select pairs in any order.

36
00:02:31,490 --> 00:02:36,230
So that's why we are able to select one comma two before four comma five.

37
00:02:36,230 --> 00:02:40,160
Because again that's not the order of the elements in the pairs array.

38
00:02:40,160 --> 00:02:41,840
But that does not matter.

39
00:02:41,840 --> 00:02:42,440
All right.

40
00:02:42,470 --> 00:02:50,450
Now first let's discuss how can we identify that this question over here is a DP or a dynamic programming

41
00:02:50,450 --> 00:02:51,080
question.

42
00:02:51,080 --> 00:02:56,540
Now what are the hints given in the question that we can use to identify this?

43
00:02:56,540 --> 00:03:04,160
Notice that in the question it says we have to find the length of the longest possible chain okay.

44
00:03:04,160 --> 00:03:07,010
So that's asking for an optimal answer.

45
00:03:07,010 --> 00:03:12,650
And then notice the question says we don't need to use up all the given intervals.

46
00:03:12,650 --> 00:03:15,260
We can select pairs in any order.

47
00:03:15,260 --> 00:03:17,660
So the question involves selection.

48
00:03:17,660 --> 00:03:21,770
And it also asks us to find an optimal answer.

49
00:03:21,770 --> 00:03:29,330
And these are two powerful hints which can help us to identify that this question over here is in fact

50
00:03:29,330 --> 00:03:31,190
a dynamic programming question.

51
00:03:31,190 --> 00:03:38,510
Now that we have identified this as a DP question, let's think about how we can identify the particular

52
00:03:38,510 --> 00:03:39,860
type of this question.

53
00:03:39,860 --> 00:03:44,960
And again, because in this course we are now dealing with less type questions.

54
00:03:44,960 --> 00:03:47,300
We know that this is an alias type question.

55
00:03:47,300 --> 00:03:50,600
But then how do we identify that in general?

56
00:03:50,600 --> 00:03:51,020
Okay.

57
00:03:51,020 --> 00:03:59,840
So notice that if we sort the array which is given to us over here, this pairs array, if we sort it

58
00:03:59,840 --> 00:04:01,220
it would look like this.

59
00:04:01,220 --> 00:04:05,570
So we have one comma two two comma nine and four comma five.

60
00:04:05,570 --> 00:04:09,290
So again let's just say that we are sorting based on the first element.

61
00:04:09,290 --> 00:04:11,660
Now we could do it even with the second element.

62
00:04:11,660 --> 00:04:17,810
But over here let's just take a look at this approach where we are sorting based on the first element.

63
00:04:17,810 --> 00:04:21,320
Now if we do that the array looks like this.

64
00:04:21,320 --> 00:04:22,370
At this point.

65
00:04:22,370 --> 00:04:31,880
And after we have done this, notice that we just need to find the longest increasing subsequence such

66
00:04:31,880 --> 00:04:35,630
that b is less than c.

67
00:04:35,630 --> 00:04:41,540
So over here we are trying to find a special type of increasing subsequence.

68
00:04:41,540 --> 00:04:48,320
Now in the typical list question we have elements like this one, two and then five.

69
00:04:49,040 --> 00:04:53,000
And then probably we have three and then we have seven.

70
00:04:53,000 --> 00:04:53,360
Okay.

71
00:04:53,360 --> 00:04:57,800
So we have elements in this manner in a typical list question.

72
00:04:57,800 --> 00:05:00,680
And we need to find the increasing subsequence.

73
00:05:00,680 --> 00:05:04,730
But over here we are not going to just consider every element.

74
00:05:04,730 --> 00:05:12,110
We have a special condition that the second element in the first array over here has to be less than

75
00:05:12,110 --> 00:05:16,700
the first element in the second array over here, or elements okay.

76
00:05:16,700 --> 00:05:18,980
We can just call it as arrays or elements.

77
00:05:18,980 --> 00:05:26,270
So we are just trying to find the length of the longest increasing subsequence with a special condition

78
00:05:26,270 --> 00:05:26,900
or rule.

79
00:05:26,900 --> 00:05:30,080
So that's why this is a dynamic programming question.

80
00:05:30,080 --> 00:05:34,580
And more specifically it's a question of the list type.

81
00:05:34,580 --> 00:05:39,830
Now in the next videos, let's go ahead and try to see how we can solve this question.

82
00:05:39,830 --> 00:05:46,190
And when we write the code for solving this question, you will see how similar this question is to

83
00:05:46,190 --> 00:05:47,780
a typical list question.

84
00:05:47,780 --> 00:05:49,160
So let's get started.