Russian Doll Envelopes
hardTime: O(n log n)Space: O(n)
Recognize the pattern
LIS on 2D envelopessort by width then LIS on heightdescending height for same width
Brute force idea
All subsets — O(2^n).
Better approach
Sort by width ASC, height DESC for same width. LIS on heights. O(n log n).
Key invariant
Descending height for same width prevents two same-width envelopes in the LIS. LIS on heights gives longest valid nesting.
Watch out for
Not sorting height descending for equal widths — allows invalid same-width pairs in the sequence.