• 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:


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 so-called 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:




The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave