Russian Doll Envelopes
hardTime: O(n log n)Space: O(n)
Signals to notice
LIS on 2D envelopessort by width then LIS on heightdescending height for same width
Brute force first
All subsets — O(2^n).
The key insight
Sort by width ASC, height DESC for same width. LIS on heights. O(n log n).
What must stay true
Descending height for same width prevents two same-width envelopes in the LIS. LIS on heights gives longest valid nesting.
Easy way to go wrong
Not sorting height descending for equal widths — allows invalid same-width pairs in the sequence.