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

2
00:00:01,460 --> 00:00:04,760
Let's now discuss how we can solve this question.

3
00:00:04,760 --> 00:00:11,600
And we will be taking the tabulation or bottom up approach for solving this question, because we are

4
00:00:11,600 --> 00:00:14,120
already familiar with the list type.

5
00:00:14,120 --> 00:00:14,480
Okay.

6
00:00:14,480 --> 00:00:20,450
So previously we have discussed the recursive approach, the memoization approach, as well as the tabulation

7
00:00:20,450 --> 00:00:23,060
approach for solving the list question.

8
00:00:23,060 --> 00:00:29,630
So let's go ahead and take a look at how we can use what we have learned over there to solve this question.

9
00:00:29,630 --> 00:00:32,150
And for this let's take an example.

10
00:00:32,150 --> 00:00:34,880
Let's say this is the array which is given to us.

11
00:00:34,880 --> 00:00:36,890
So it has three elements.

12
00:00:36,890 --> 00:00:43,100
And each element is such that the first element in that particular array has the lower value.

13
00:00:43,100 --> 00:00:48,920
For example over here notice four is less than five, two is less than nine, and one is less than two.

14
00:00:48,950 --> 00:00:52,070
Now the first step is to sort this.

15
00:00:52,070 --> 00:00:55,910
And we have discussed in the previous video why we need to do this.

16
00:00:55,910 --> 00:01:00,860
So once we have sorted these elements this is how the array would look like.

17
00:01:00,860 --> 00:01:05,060
Notice we have one over here, two over here and four over here.

18
00:01:05,150 --> 00:01:10,880
Now once we are done sorting the array which is given to us, we will have a DP array.

19
00:01:10,880 --> 00:01:15,260
And initially we will fill each cell with the value one.

20
00:01:15,260 --> 00:01:17,120
So over here we have three elements.

21
00:01:17,120 --> 00:01:23,300
So that's why in the DP array we have three cells and each value is filled with one.

22
00:01:23,300 --> 00:01:30,410
Now notice that this is the same thing that we did for the tabulation approach, the 1D tabulation approach

23
00:01:30,410 --> 00:01:32,870
when we discussed the list question.

24
00:01:32,870 --> 00:01:36,380
So what we will do is we'll have a nested for loop.

25
00:01:36,380 --> 00:01:43,820
So one variable would be I and I will go from the value one up to the last index okay.

26
00:01:43,820 --> 00:01:46,610
So in this case that's one up to two.

27
00:01:46,610 --> 00:01:52,670
And for each value of I j will take the values zero to I minus one.

28
00:01:52,670 --> 00:01:57,320
This is exactly the same thing that we did for the list question.

29
00:01:57,320 --> 00:02:03,710
And at every point or for every combination of I and J, we will check two things.

30
00:02:03,710 --> 00:02:05,600
Now let's take an example.

31
00:02:05,600 --> 00:02:10,010
Let's say I is over here and J is over here okay.

32
00:02:10,010 --> 00:02:17,960
So at this point we will check whether this value over here is less than this value, because that's

33
00:02:17,960 --> 00:02:23,330
the condition mentioned in the question for forming a chain of pairs okay.

34
00:02:23,330 --> 00:02:26,180
And over here we see that that's not the case.

35
00:02:26,180 --> 00:02:36,530
But let's say if it was the case then we would also check whether depee at J plus one is greater than

36
00:02:36,530 --> 00:02:38,090
depee at I.

37
00:02:38,210 --> 00:02:38,720
Okay.

38
00:02:38,720 --> 00:02:42,350
Remember this is the same thing that we did in the list question as well.

39
00:02:42,350 --> 00:02:46,670
So let's go ahead and see how the algorithm solves this question.

40
00:02:46,670 --> 00:02:50,570
So initially I is equal to one and j takes the value zero.

41
00:02:50,570 --> 00:02:52,790
And we are comparing these two values.

42
00:02:52,790 --> 00:02:57,800
We see that this value over here is not less than this value okay.

43
00:02:57,800 --> 00:03:04,670
And because of that reason we will not be able to form a chain of pairs using these two elements.

44
00:03:04,670 --> 00:03:07,130
Therefore we move forward.

45
00:03:07,130 --> 00:03:13,070
So I takes the value two and j will take the values zero as well as one.

46
00:03:13,070 --> 00:03:15,680
So initially j takes the value zero.

47
00:03:16,250 --> 00:03:23,780
Now we will check whether this value over here is less than this value which is the case okay two is

48
00:03:23,780 --> 00:03:24,590
less than four.

49
00:03:24,590 --> 00:03:30,710
So that means that we can form a chain of pairs where this is the first element.

50
00:03:30,710 --> 00:03:33,380
And this over here is the second element.

51
00:03:33,380 --> 00:03:40,790
Now we also need to check whether depee at j plus one is greater than depee at I.

52
00:03:40,790 --> 00:03:41,210
Okay.

53
00:03:41,210 --> 00:03:47,120
So at this point depee at j is this value over here because j is pointing at index zero.

54
00:03:47,120 --> 00:03:50,300
So we have zero over here, one over here and two over here.

55
00:03:50,300 --> 00:03:53,600
And we have zero over here, one over here and two over here.

56
00:03:53,600 --> 00:03:56,630
So depee at J is this value.

57
00:03:56,630 --> 00:04:03,680
And one plus one which is two is in fact greater than depee at I which is this value which is just one.

58
00:04:03,680 --> 00:04:05,300
So two is greater than one.

59
00:04:05,300 --> 00:04:12,500
Therefore we are going to modify the value of dp at I, and we will set it to dp at j plus one.

60
00:04:12,560 --> 00:04:13,220
Okay.

61
00:04:13,220 --> 00:04:14,690
And then we move forward.

62
00:04:14,690 --> 00:04:18,080
So j over here took the value zero.

63
00:04:18,080 --> 00:04:20,930
Now when we move forward j will take the value one.

64
00:04:20,930 --> 00:04:25,700
And at this point again we're going to check whether this value is less than this value.

65
00:04:25,700 --> 00:04:28,190
And we see that that's not the case okay.

66
00:04:28,190 --> 00:04:32,870
And therefore we can't make a chain of pairs using these two elements.

67
00:04:32,870 --> 00:04:37,250
And again because we have reached the last value for I we are done.

68
00:04:37,250 --> 00:04:37,670
Okay.

69
00:04:37,670 --> 00:04:41,450
Now we have this updated DP array over here.

70
00:04:41,450 --> 00:04:46,100
And we will just find the maximum value among all these elements.

71
00:04:46,100 --> 00:04:48,080
And that is our answer.

72
00:04:48,080 --> 00:04:54,740
So in this case we are getting a length of two which is the chain of pairs where we have one comma two

73
00:04:54,740 --> 00:04:58,160
and then we have four comma five okay.

74
00:04:58,160 --> 00:04:59,810
And the length of this.

75
00:05:00,230 --> 00:05:02,510
Chain of pairs is equal to two.

76
00:05:02,510 --> 00:05:10,790
So this is the bottom up or tabulation approach which we can use to solve the max pair chain problem.

77
00:05:10,790 --> 00:05:16,940
In the next video, let's discuss the complexity analysis of the approach that we have discussed over

78
00:05:16,940 --> 00:05:17,330
here.