Russian Doll Envelopes
Application of Longest Increasing Subsequence

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Note:
Rotation is not allowed.
Example:
Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Solution:
 Recall from Longest Increasing Subsequence
chapter that
most problems where
you are given an array (or list) of items and you'd have to find the largest subset of the items which maintains certain given condition
could be solved using Longest Increasing Subsequence technique.
This problem has striking similarity with Box Stacking, and just like Box Stacking this problem is also a great use case for Longest Increasing Subsequence concept.
The problem statement says one envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
This means is envelope E1 can fit into envelope E2 then:
 width of E2 > width of envelope E1
 height of E2 > height of E1
From above relations we get:
(width of E2 * height of E2) > (width of E1 * height of E1)
or, Surface Area of E2
>
Surface Area of E1
Once we sort all the envelopes in ascending order of their surface area, the Longest Increasing Subsequence of the sorted envelopes will give the maximum number of envelopes that can be Russian dolled.
In many places I have seen they mark this problem as
hard
, in fact if you haven't realized the potential of
Longest Increasing Subsequence.
technique or have not done enough research and practice to appreciate it's applications and potential,
this problem may come off as hard. But once you recognize that this problem is
Longest Increasing Subsequence concept,
it becomes very easy to solve. This is why I stress so much on getting a deep understanding
of the classic problems like Longest Increasing Subsequence,
which many of us take lightly thinking they are easy. They are easy,
but what is hard to master is to realize and gain a strong understanding of the wide applications of
these classic techniques/concepts and the problems that
can be solved using these techniques. Almost none of these
classic problems are unheard of, in fact almost all of us have learned about
these classic problems (like Knapsack Problem, Longest Increasing Subsequence Problem, Matrix Multiplication problem etc)
at school and somehow the we are taught at school that we fail to
appreciate the huge potential of these classic problems in solving other much more complex problems. At
The Algorists my goal is to
bridge this gap. Almost all the algorithmic problems asked in technical interviews could be easily solved
if you have a strong grip on all these classic problems. In fact, if you closely notice, you
would find that each classic problem even comes with its own code template (the onus of finding out or deriving
the template is definitely on us) that you can use for solving most related problems. For
example: look how the solution for this problem looks so similar to that of
Box Stacking. In both the cases you
are sorting the given arrays based on areas, and I have also discussed the rationale behind it above. I have
seen many people stumbling on how to sort the array implementing the logic on
how to sort the array. Instead of taking area they think in a much convoluted way unnecessarily. Simplicity is the key.
You will see in many chapters here at
The Algorists how many socalled hard problems can be solved easily
when you know exactly what you are doing, and the key is to know the core concepts and the classic problems by heart, which is not that hard to
accomplish.
Code:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Other related chapters:
 Core Concept
 Box Stacking
 Largest Divisible Subset
 Longest String Chain
 Best Team with No Conflict
 Longest Bitonic Subsequence
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn