Welcome back.
We have another interesting question over here which is called the Russian doll envelopes question.
The question reads you are given a 2D array of integers envelopes where envelopes at position I is this
element over here.
Notice that each element in the envelopes array is an array in itself with two values.
Okay, so w I is the width of the ith element and h I is the height of the ith element.
Okay, so where envelopes at index I represents the width and height of an envelope, one envelope can
fit into another if and only if both the width and height of one envelope are greater than the other
envelopes.
Width and height.
Return the maximum number of envelopes you can.
Russian doll that is put one inside the other.
Note you cannot rotate an envelope.
So this is the question over here.
It says that you can fit one envelope into another only if the width and height is strictly lesser than
the width and height of the other envelope.
For example, over here we have this envelope, and from this image it's clear that the width over here
is less than the width of this envelope, as well as the height of this envelope is less than the height
of this envelope.
So as per the condition mentioned over here, we will be able to put this envelope inside it.
Okay.
So we have this envelope over here.
And outside this envelope we have the bigger one.
So this process is what we call Russian doll okay.
So that's the question over here.
And then we are also given an example.
And the question asks us to find the maximum number of envelopes that we can Russian doll.
So in this example which is given to us notice we have one comma two.
And then we have four comma three.
And then we have five comma six okay.
So this is the array which is given to us.
But among these four envelopes which are there in this array we are able to Russian doll three envelopes
in this manner.
So this would be the envelope in the deepest layer.
And above it we have this envelope.
And on the outside we have this envelope over here.
And again notice one is less than four and two is less than three.
Similarly four is less than five and three is less than six.
So the condition mentioned over here is satisfied.
Now again remember the question also says that you cannot rotate an envelope, which means that you
cannot interchange the width and height so as to be able to insert one envelope into another.
Now, if you could rotate an envelope, this question would be pretty similar to another famous coding
interview question, which is called the box stacking problem.
Okay, but that's not the case over here.
All right.
So we have understood the question and we also have taken a look at the example which is given to us.
Now remember it's very important that you ask any clarifying questions which you may want to ask.
Now one question you could ask is if an empty array is given, does the output have to be zero?
And let's say the interviewer replies, you will not be given an empty array.
Okay, so there will be at least one envelope.
You could also ask, or maybe you could just clarify that.
What if two envelopes are of the same size?
My understanding is that I will not be able to insert this envelope into another envelope, which has
the same size as this envelope over here.
And let's say the interviewer says, yes, your understanding is correct.
So we have understood the question, and we have also asked any clarifying questions which we wanted
to ask.
Let's now proceed and try to solve this question.
The first thing that we need to do is we need to be able to identify what pattern of question this is.
Let's try to see whether there are any hints in the question which is given to us, which we can use
to identify this first as a dynamic programming question.
Notice over here it says return the maximum number of envelopes.
Okay.
So this means that we are asked to find an optimal solution, which is a strong hint that probably we
could use dynamic programming to solve this question.
We also have choices in this question okay.
We could either include or pick a particular envelope, or we can just not pick it or exclude it.
So we have choices.
And we are also asked to find the optimal solution.
So these are two powerful hints which we can use to identify that.
This in fact is a dynamic programming question.
And maybe it's a variation of the longest increasing subsequence question.
Pattern, because we need to identify a sequence of envelopes such that one envelope is in another envelope.
Now let's discuss more of this in the next video, where we will be brainstorming the approach that
we can take to solve this question.