Russian Doll Envelopes
HardMath
Description
Given envelopes with (width, height), find the maximum number that can be nested (smaller width AND height fits inside larger).
Examples
Input:
envelopes = [[5,4],[6,4],[6,7],[2,3]]Output:
3Explanation:
[2,3] -> [5,4] -> [6,7]
Input:
envelopes = [[1,1]]Output:
1Explanation:
With only one envelope, the maximum nesting depth is 1 since there are no other envelopes to nest inside.
Input:
envelopes = [[4,5],[4,6],[6,7],[8,4],[8,6]]Output:
2Explanation:
The longest valid chain has length 2, for example [4,5] -> [6,7]. Envelopes with equal widths cannot be nested.
Constraints
- •
1 ≤ envelopes.length ≤ 10⁵ - •
envelopes[i].length == 2
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.