# Clean and short nlogn solution

• See more explanation in Longest Increasing Subsequence Size (N log N)

``````def maxEnvelopes(self, envelopes):
def bin_search(A, key):
l, r = 0, len(A)
while l < r:
mid = (l+r)/2
if A[mid][1] < key[1]:
l = mid + 1
else:
r = mid
return l
envelopes.sort(
cmp = lambda x,y: x[0]-y[0] if x[0] != y[0] else y[1]-x[1])
n = len(envelopes)
tails = []
for i in range(n):
e = envelopes[i]
p = bin_search(tails, e)
if p == len(tails):
tails.append(e)
else:
tails[p] = e
return len(tails)
``````

``````bool cmp(pair<int, int> &p1, pair<int, int> &p2) {
return p1.first < p2.first || p1.first == p2.first && p1.second > p2.second;
}

int maxEnvelopes(vector<pair<int, int>> &envelopes) {
if (envelopes.size() < 2) {
return envelopes.size();
}

sort(envelopes.begin(), envelopes.end(), cmp);

vector<pair<int, int>> maxLenWithMin(envelopes.size() + 1);
int maxLen = 1;
maxLenWithMin[1] = envelopes[0];
for (int i = 1; i < envelopes.size(); i++) {
int index = binarySearch(maxLenWithMin, maxLen, envelopes[i]);
if (index > maxLen) {
maxLen++;
}
maxLenWithMin[index] = envelopes[i];
}

return maxLen;
}

// a[i-1] < b =< a[i], return i
int binarySearch(vector<pair<int, int>> &maxLenWithMin, int maxLen,
pair<int, int> &target) {
int l = 1;
int r = maxLen;

if (target.second > maxLenWithMin[r].second) {
return r + 1;
}

if (target.second <= maxLenWithMin[l].second) {
return l;
}

while (l + 1 != r) {
int mid = l + (r - l) / 2;
if (target.second > maxLenWithMin[mid].second) {
l = mid;
} else {
r = mid;
}
}

return r;
}
``````

• Nice solution! I had a similar solution, but never get it right, as I sorted envelopes by using the default comparing function,
the y[1]-x[1] part in cmp = lambda x,y: x[0]-y[0] if x[0] != y[0] else y[1]-x[1] is actually very important!

Here is my solution with your cmp function, works finally :)

``````def maxEnvelopes(envelopes):
envelopes.sort(
cmp = lambda x,y: cmp(x[0], y[0]) if x[0] != y[0] else cmp(y[1], x[1]))
lst = [x[1] for x in envelopes]
tails = []
for e in lst:
p = bisect.bisect_left(tails, e)
if p == len(tails):
tails.append(e)
else:
tails[p] = e
return len(tails)``````

• So, here is an even shorter version, using `lambda` for sorting and `bisect.bisect_left` for binary search.

``````import bisect
class Solution(object):
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
envelopes.sort(key = lambda x: (x[0], -x[1]))

dp = []
for x in envelopes:
i = bisect.bisect_left(dp, x[1])
if i == len(dp):
dp.append(x[1])
else:
dp[i] = x[1]

return len(dp)
``````

• ``````class Solution(object):
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
envelopes.sort(key=lambda x: (x[0], -x[1]))
dp = [sys.maxsize] * len(envelopes)
for e in envelopes:
dp[bisect.bisect_left(dp, e[1])] = e[1]
return bisect.bisect_left(dp, sys.maxsize)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.