Welcome back.
Let's now implement the code for solving the max length of pair chain.
Question.
Now in the question it's mentioned that two elements a comma b and c comma d can be considered to be
a chain of pairs if b is less than C, and we already know that these elements are such that the first
element will be less than the second element, or, for example, a would be less than b, and c would
be less than d.
All right.
Now let's get started.
First, let's go ahead and sort the pairs array which is given to us.
And we have discussed in detail in the previous video why this is required okay.
So let's do that.
And we are going to sort in ascending order using the first element of the array elements.
All right.
And let's say n is the number of pairs that are there in the pairs array.
So I can say let n is equal to pairs dot length.
And we will also need a DP array which is going to be a 1D array which has the same size.
And let's fill every value in the array over here with one.
Now this is similar to what we have discussed for the list question for the 1D tabulation approach.
That's the approach we are going to implement over here, because this is the pattern that we have already
discussed and we are very familiar with.
And we will also need a variable.
Let's just call it rest or max.
We can call it max.
So this would be the length of the maximum number of elements that we are able to chain.
Okay.
Now initially max is going to equal one because we can have always the minimal chain length of one by
just taking one element.
And finally after we find the number of elements that we are able to chain, we will just return Max.
Okay.
So this is the approach that we are taking over here.
Now let's implement the same thing that we have discussed when we discussed the 1D tabulation approach
for the list question.
So I am going to iterate over the elements in the DP array.
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
zero up to I minus one.
So I can say for let j is equal to zero j less than I j plus plus.
And now we are going to compare the arrays at index j and at index I.
And what we are going to check is whether the element at index one over here is less than the element
at index zero over here.
So that's the criteria which is mentioned over here.
For us to be able to create a chain of pairs.
Right.
So that's what we are checking over here.
And if this is true then we will also check whether depee at J plus one is greater than depee at I.
Okay.
So this is the criteria that we need to check.
Now let's just complete the syntax.
So if this is true then we would say that dp at index I is equal to dp at index j plus one.
And in this way we are forming a new chain by extending the chain ending at index j.
Now this is the same thing that we did when we implemented the 1D tabulation approach for solving the
list question.
Now there's one more thing that we need to do now once we are out of this okay.
Once we are out of this for loop over here, we have to check whether the value for DP at I is greater
than the value currently in the variable max.
So we can say if dp at I is greater than max.
Okay.
So if this is the case, then max would be equal to dp at I.
And this allows us to avoid passing through or iterating through the DP array one more time okay.
Because we directly get the maximum value over here.
And therefore we would just need to return max over here.
And that's it.
So this should take care of this.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.