354. Russian Doll Envelopes
hardHow many envelopes can fit one inside another? Reduces to LIS in one dimension after a clever sort trick that handles width ties.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope. One envelope can fit into another if and only if both the width and height of one envelope are strictly greater than the other envelope's width and height. Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other). Note: You cannot rotate an envelope.
Constraints
1 <= envelopes.length <= 10^5envelopes[i].length == 21 <= wi, hi <= 10^5
Examples
Example 1
envelopes = [[5,4],[6,4],[6,7],[2,3]]3Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Example 2
envelopes = [[1,1],[1,1],[1,1]]1Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Sort by width ascending. Now we need a strictly-increasing chain on heights — that's LIS.
Hint 2
Tie-breaker for equal widths: sort heights DESCENDING. That prevents two equal-width envelopes from both being picked.
Hint 3
Run patience-sort LIS on the height column in O(n log n).
Solution approach
Reveal approach
Sort envelopes by width ascending. The trick: for ties on width, sort heights DESCENDING so that two envelopes with the same width can never both be selected (a longer height followed by a shorter height is not strictly increasing). Then extract the heights into a 1D array and run patience-sort LIS in O(n log n). Maintain tails[], where tails[k] is the smallest tail of any increasing subsequence of length k+1. For each height h, binary-search the leftmost index in tails with value >= h and replace it (or append if h is bigger than all). The final length of tails is the answer.
Complexity
- Time
- O(n log n)
- Space
- O(n)
Related patterns
- lis
- patience-sort
- sorting
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
Practice these live with InterviewChamp.AI
Drill Russian Doll Envelopes and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →