# Sort pairs by first element then find LIS in second element O(nlogn)

• The only tricky part is to make sure envelopes with same width should not be counted towards the LIS sequence, for that, we use a custom sort function that returns true iff

A.first < B.first || (A.first == B.first && A.second > B.second)

``````class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
if (envelopes.empty())
return 0;

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

vector<int> table;
table.push_back(envelopes[0].second);
// below is binary search for LIS
for (int i = 1; i < envelopes.size(); i++){
if (envelopes[i].second > table[table.size() - 1])
table.push_back(envelopes[i].second);
else
table[lower_bound(table.begin(), table.end(), envelopes[i].second) - table.begin()]= envelopes[i].second;
}

return table.size();
}

static bool cmpPair(const pair <int, int> &a, const pair <int, int> &b){
return a.first < b.first || (a.first == b.first && a.second > b.second);// a.second > b.second makes sure same width envelops won't be counted towards the LIS sequence in height :p
}
};
``````

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