1
00:00:00,110 --> 00:00:01,130
Welcome back.

2
00:00:01,160 --> 00:00:05,690
Let's now implement the code for solving the max length of pair chain.

3
00:00:05,690 --> 00:00:06,290
Question.

4
00:00:06,290 --> 00:00:12,680
Now in the question it's mentioned that two elements a comma b and c comma d can be considered to be

5
00:00:12,680 --> 00:00:20,180
a chain of pairs if b is less than C, and we already know that these elements are such that the first

6
00:00:20,180 --> 00:00:25,730
element will be less than the second element, or, for example, a would be less than b, and c would

7
00:00:25,730 --> 00:00:26,450
be less than d.

8
00:00:26,450 --> 00:00:26,840
All right.

9
00:00:26,870 --> 00:00:28,070
Now let's get started.

10
00:00:28,070 --> 00:00:32,420
First, let's go ahead and sort the pairs array which is given to us.

11
00:00:32,420 --> 00:00:37,280
And we have discussed in detail in the previous video why this is required okay.

12
00:00:37,280 --> 00:00:38,510
So let's do that.

13
00:00:38,510 --> 00:00:44,450
And we are going to sort in ascending order using the first element of the array elements.

14
00:00:44,450 --> 00:00:45,200
All right.

15
00:00:45,200 --> 00:00:49,730
And let's say n is the number of pairs that are there in the pairs array.

16
00:00:49,730 --> 00:00:53,630
So I can say let n is equal to pairs dot length.

17
00:00:54,770 --> 00:01:02,450
And we will also need a DP array which is going to be a 1D array which has the same size.

18
00:01:02,450 --> 00:01:06,590
And let's fill every value in the array over here with one.

19
00:01:06,860 --> 00:01:12,200
Now this is similar to what we have discussed for the list question for the 1D tabulation approach.

20
00:01:12,200 --> 00:01:16,430
That's the approach we are going to implement over here, because this is the pattern that we have already

21
00:01:16,430 --> 00:01:18,170
discussed and we are very familiar with.

22
00:01:18,170 --> 00:01:20,450
And we will also need a variable.

23
00:01:20,450 --> 00:01:22,940
Let's just call it rest or max.

24
00:01:22,940 --> 00:01:23,990
We can call it max.

25
00:01:23,990 --> 00:01:28,310
So this would be the length of the maximum number of elements that we are able to chain.

26
00:01:28,310 --> 00:01:28,730
Okay.

27
00:01:28,730 --> 00:01:35,990
Now initially max is going to equal one because we can have always the minimal chain length of one by

28
00:01:35,990 --> 00:01:37,460
just taking one element.

29
00:01:37,460 --> 00:01:44,090
And finally after we find the number of elements that we are able to chain, we will just return Max.

30
00:01:44,090 --> 00:01:44,600
Okay.

31
00:01:45,050 --> 00:01:47,450
So this is the approach that we are taking over here.

32
00:01:47,450 --> 00:01:53,120
Now let's implement the same thing that we have discussed when we discussed the 1D tabulation approach

33
00:01:53,120 --> 00:01:54,560
for the list question.

34
00:01:54,560 --> 00:01:57,710
So I am going to iterate over the elements in the DP array.

35
00:01:57,710 --> 00:02:06,050
So I can say for let I is equal to one I in less than n, I plus, plus and j will take the values from

36
00:02:06,050 --> 00:02:07,880
zero up to I minus one.

37
00:02:07,880 --> 00:02:14,450
So I can say for let j is equal to zero j less than I j plus plus.

38
00:02:15,380 --> 00:02:22,550
And now we are going to compare the arrays at index j and at index I.

39
00:02:22,880 --> 00:02:30,290
And what we are going to check is whether the element at index one over here is less than the element

40
00:02:30,290 --> 00:02:32,660
at index zero over here.

41
00:02:33,080 --> 00:02:35,450
So that's the criteria which is mentioned over here.

42
00:02:35,450 --> 00:02:38,720
For us to be able to create a chain of pairs.

43
00:02:38,720 --> 00:02:39,140
Right.

44
00:02:39,140 --> 00:02:40,700
So that's what we are checking over here.

45
00:02:40,700 --> 00:02:49,460
And if this is true then we will also check whether depee at J plus one is greater than depee at I.

46
00:02:49,790 --> 00:02:50,150
Okay.

47
00:02:50,150 --> 00:02:52,640
So this is the criteria that we need to check.

48
00:02:52,640 --> 00:02:54,410
Now let's just complete the syntax.

49
00:02:54,410 --> 00:03:04,280
So if this is true then we would say that dp at index I is equal to dp at index j plus one.

50
00:03:04,280 --> 00:03:09,920
And in this way we are forming a new chain by extending the chain ending at index j.

51
00:03:09,920 --> 00:03:15,470
Now this is the same thing that we did when we implemented the 1D tabulation approach for solving the

52
00:03:15,470 --> 00:03:16,460
list question.

53
00:03:16,460 --> 00:03:21,020
Now there's one more thing that we need to do now once we are out of this okay.

54
00:03:21,020 --> 00:03:27,680
Once we are out of this for loop over here, we have to check whether the value for DP at I is greater

55
00:03:27,680 --> 00:03:30,980
than the value currently in the variable max.

56
00:03:30,980 --> 00:03:36,170
So we can say if dp at I is greater than max.

57
00:03:37,580 --> 00:03:37,970
Okay.

58
00:03:37,970 --> 00:03:42,050
So if this is the case, then max would be equal to dp at I.

59
00:03:42,050 --> 00:03:47,780
And this allows us to avoid passing through or iterating through the DP array one more time okay.

60
00:03:47,780 --> 00:03:50,510
Because we directly get the maximum value over here.

61
00:03:50,510 --> 00:03:53,450
And therefore we would just need to return max over here.

62
00:03:53,450 --> 00:03:54,110
And that's it.

63
00:03:54,110 --> 00:03:56,090
So this should take care of this.

64
00:03:56,090 --> 00:03:59,720
Now let's go ahead and run this code and see if it's passing all the test cases.

65
00:04:01,110 --> 00:04:02,880
And you can see that it's working.

66
00:04:02,880 --> 00:04:04,650
It's passing all the test cases.