In the previous video, we have understood the Russian doll question.
Now let's try to brainstorm how we can solve this question.
So for this, let's take an example.
Let's say this is the array which is given to us.
And finally we'll have to identify this sequence because again this is the maximum number of envelopes
you can select such that you are able to put one envelope in another envelope okay.
So the criteria is that if we want to be able to put one envelope into another, then the width and
height of the first envelope has to be lesser than the width and the height of the other envelope.
Okay.
So now let's see how we can solve this question just by sorting the envelopes which are given to us,
and then by applying the alias algorithm.
So let's take a look at that again.
Let's use an example.
So if this is the array which is given to us.
And notice that every element in this array has two elements.
So the first element represents the width of this particular envelope.
And the second value over here represents the height of this particular envelope.
Now if we go ahead and sort these envelopes by their first value which is two, seven, six and five,
this is how the array would look like.
So two comma three.
And then you have five comma four six comma five and seven comma one.
Notice that these values are now in increasing order.
Now because these values are currently in increasing order, all that we need to do is to apply the
alias algorithm on the second element in each of these.
Okay.
That is we are going to apply the alias algorithm thinking only of these values three, four, five
and one.
Okay.
Now if I take these four values, notice that I am able to form an increasing sequence.
If I were to just select these three okay.
And when I just select these three automatically I am also considering their respective widths because
again this is the width.
This is the height right now because the widths are already in increasing order.
If I can just select values that form an increasing sequence with respect to the heights, we already
get three elements in a way that you are able to Russian doll them, and therefore the answer over here
is equal to three.
Okay, now again this is just the first part where we develop the intuition with respect to why this
approach works, where we sort the envelopes and then apply the alias algorithm on the second element.
But there are a few more nuances that we may need to consider.
Now what if instead of five over here we had six?
Okay.
So this element is now six comma four.
Now in this case if we sort it right we would still have the values in this order because these two
values are just equal okay.
So we have 266 and seven.
And these values are sorted okay.
So when we have six over here these are the elements in the envelopes array.
And we have seen that they are already sorted.
But then our algorithm in this case will not work.
Why is that so.
Because we have got it in this manner after sorting.
And then when we try to apply alias on the second elements, okay, we think that we are getting three
elements in increasing order.
But the answer in this case is not three, because these two values are equal and therefore we are not
able to insert one envelope in the other.
Now, to solve this problem, we can approach it in two ways.
The first method that we can use is before including an element in the longest increasing subsequence
that we are forming, we will not only check the values at index one, which is the case as we saw over
here, but rather we will check both the values at index one as well as at index zero.
Okay, so in this case we would be able to see that these two are not increasing and therefore we will
not include them in the Russian doll.
So this is one way that we can solve this.
And the second way is that if we find elements that are equal, when we are sorting the array which
is given to us, we will sort those elements using the values at index one, which is this value and
this value in descending order.
Okay.
So when we do that the array after sorting would look like this.
Notice we have sorted these two values in descending order.
So that's why we have five over here.
And then.
For over here, and then we would just need to apply the list algorithm on the second element, which
is three, five, four and one.
And when we do that, we get the answer as two, because we see that two is less than six and three
is less than five.
And we are able to Russian doll only these two envelopes.
So these are the two ways that we can solve this question.
And when we apply Liz, on the second element, we can use any of the methods that we have previously
discussed.
We can use the tabulation approach, the memoization approach.
And we can also use the binary search variant of Liz okay.
In fact, this variant will give us the best time complexity.