DSA problem
Russian Doll Envelopes
You are given a 2D array of envelopes envelopes[i] = [w_i, h_i] representing the width and height of each envelope. One envelope can fit into another if and only if both its width and height are strictly smaller than those of the outer envelope. Rotation is not allowed. Return the maximum number of envelopes you can nest one inside another, like a set of Russian dolls.
A first instinct is to sort the envelopes lexicographically by (w, h) and run a 2D LIS, but that produces an O(n²) algorithm that is too slow for the typical constraint n <= 10^5. We can do better by reducing the 2D problem to a 1D LIS through a careful sort.
Sort the envelopes by width in ascending order. For envelopes that share the same width, sort their heights in descending order. The descending tie-breaker is critical: it prevents two envelopes with equal width from forming a chain in the subsequent height-LIS, because a strictly increasing run on the heights cannot pick two of them (the second would be smaller, not larger). After this sort, any strictly increasing subsequence of heights automatically corresponds to envelopes whose widths are also strictly increasing.
Now extract the heights into an array and compute the standard Longest Increasing Subsequence length on that array, using the O(n log n) patience-sort + binary search algorithm. The result is the maximum number of nesting envelopes. Total complexity is O(n log n) time and O(n) space.
Examples
envelopes = [[5,4],[6,4],[6,7],[2,3]]3envelopes = [[1,1],[1,1],[1,1]]1envelopes = [[4,5],[4,6],[6,7],[2,3],[1,1]]4Constraints
- 1 <= envelopes.length <= 10^5
- envelopes[i].length == 2
- 1 <= w_i, h_i <= 10^5
- Both width and height must be strictly smaller for an envelope to fit inside another (no rotation allowed).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.