298. Russian Doll Envelopes
You are handed a list envelopes where entry i is a pair [wᵢ, hᵢ] — the width and height of one envelope. Envelope A slides inside envelope B only when both of A's dimensions are strictly smaller than B's; matching on either dimension means it does not fit, and rotating an envelope is not allowed.
Return a single integer: the greatest number of envelopes you can nest one inside the next, Russian-doll style.
Example 1:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The chain [2,3] → [5,4] → [6,7] nests three envelopes. [6,4] cannot extend it: it shares a width with [6,7] and a height with [5,4].
Example 2:
Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
Explanation: Identical envelopes never fit inside each other, so the best chain is a single envelope.
Constraints:
- 1 ≤ envelopes.length ≤ 10⁵
- 1 ≤ wᵢ, hᵢ ≤ 10⁹
- Both dimensions must be strictly smaller for one envelope to fit in another; no rotation.
Hints:
Sorting by width almost turns this 2-D question into a 1-D one: after sorting, you only need an increasing chain of heights. But what goes wrong when two envelopes share a width?
Sort widths ascending and, on width ties, heights **descending**. Then two same-width envelopes can never both appear in a strictly increasing height sequence — the problem collapses into plain Longest Increasing Subsequence over the heights.
LIS in O(n log n): keep tails[k] = the smallest height that can end an increasing chain of length k+1, and place each new height with a binary search (lower_bound / bisect_left for strict increase).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Expected output: 3