# Simple and short, easy to understand LIS based solution C++. time= O(NlogN), Space= O(N)

• ``````Logic:
1. Sort the list by either w (or h) as key.(take care of equal case)
2. Apply LIS on sorted list with h(or w) as key.(take care of equal case)

static bool comp(pair<int, int> a, pair<int, int> b) //sort on the basis of w as key
{
if(a.first == b.first)
return a.second<b.second; // sort entries with h as key when w is same
return a.first<b.first;
};
class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), comp); // sort the vector
vector<int>LIS(envelopes.size(),1);
int maxx =0;
if(envelopes.size()>0)
maxx=1;
for(int i =1; i<envelopes.size() ;i++)
{
for(int j =0; j<i; j++)
{
if(envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second && LIS[i]<LIS[j]+1) // takes care of == case of w in sorted list
{
LIS[i] = LIS[j]+1;
maxx = max(maxx,LIS[i]);
}
}
}
return maxx;

}
};``````

• this is N^2 , not NlogN

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