Welcome back.
Let's now get into the code for solving the Russian doll envelopes.
Question.
As we have discussed in the previous video, it's pretty straightforward.
We just need to sort the envelopes given to us and then apply the Lis algorithm on the second element.
Okay.
So let's get started.
So we're going to sort the envelopes array by width in ascending order and by height in descending order
if the widths are the same okay.
So let's do that.
Okay, now let's say n is the length of the envelopes array.
And let's create a DP array which will have the same size as the envelopes array which is given to us.
And we are going to fill every cell in this DP with the value one.
And we'll also need a max variable to track the longest increasing subsequence.
And finally we will be returning this.
All right.
So this is the approach that we are taking.
And all that remains is to apply the NIST algorithm on the second element.
Okay.
Again the envelopes array has arrays as elements.
And in each element array we will just be taking a look at the second element to apply the Liz algorithm.
So I can say for let I is equal to one I less than n I plus plus for let j is equal to zero j less than
I, because j has to take the values from zero up to I minus one for a value of I okay and j plus plus.
And now we are going to see whether envelopes at index I at index one, because we are taking a look
at the second element in this particular array is greater than envelopes at index j at one okay.
And if this is the case then we will check whether depee at J plus one is greater than DP at I.
And if both of these are true then we will say dp at I is equal to tp at j plus one.
Notice this is exactly the nice algorithm implemented, right?
This is what we have discussed when we discuss the 1D tabulation approach for the nice question.
Now, after we are through and after we have identified DP at I.
Okay, so after we have gone through all the possible J's for a value of I, we have to check whether
DP at I is greater than max, because if that is the case, then over here we can just assign max to
be equal to dp at I.
And this helps us to identify the maximum value in the DP array without having to iterate through it
one more time.
Okay.
And then we are just returning Max over here and that's it.
This should solve the question.
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.
Now also do try to implement the binary search variant of Lis in this question.
That would be a great practice and I will provide the code for that as an article.