## Russian Doll Envelopes

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(begin(envelopes), end(envelopes), [](const auto& a, const auto& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
});

// same as 300. Longest Increasing Subsequence
int ans = 0;
vector<int> dp(envelopes.size());

for (const auto& e : envelopes) {
int l = 0;
int r = ans;
while (l < r) {
const int m = (l + r) / 2;
if (dp[m] >= e[1])
r = m;
else
l = m + 1;
}
dp[l] = e[1];
if (l == ans)
++ans;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

// same as 300. Longest Increasing Subsequence
int ans = 0;
int[] dp = new int[envelopes.length];

for (int[] e : envelopes) {
int i = Arrays.binarySearch(dp, 0, ans, e[1]);
if (i < 0)
i = -(i + 1);
dp[i] = e[1];
if (i == ans)
++ans;
}

return ans;
}
}
``````

## Python

``````class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
# same as 300. Longest Increasing Subsequence
ans = 0
dp = [0] * len(envelopes)

for _, h in envelopes:
l = 0
r = ans
while l < r:
m = (l + r) // 2
if dp[m] >= h:
r = m
else:
l = m + 1
dp[l] = h
if l == ans:
ans += 1

return ans
``````