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]]Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
envelopes = [[4,5],[4,6],[6,7],[8,4],[8,6]]Output:
3Explanation:
The longest chain is [4,5]->[8,6]->[6,7]. Note that [4,6] cannot follow [4,5] because widths are equal (strictly smaller width AND height are required). The maximum nesting depth is 3.
Constraints
- •
1 ≤ envelopes.length ≤ 10⁵ - •
envelopes[i].length == 2