Dynamic Programming
LC #354Hard
Russian Doll Envelopes
Dynamic Programming
GoogleAmazonBloombergProblem
Find the maximum number of envelopes you can nest (each must be strictly larger in both dimensions).
dynamic-programmingbinary-searchsorting
Constraints
- ›1 ≤ envelopes.length ≤ 10⁵
- ›envelopes[i].length == 2
- ›1 ≤ wi, hi ≤ 10⁵
Example
Input
envelopes = [[5,4],[6,4],[6,7],[2,3]]Output
3Why
[2,3] → [5,4] → [6,7] — each strictly fits inside the next