✅C++ | ✅2 Approaches well Explained O(N^2) & O(NlogN) | ✅Easy & clean Code
Approach-1: O(N^2) Approach | passed 85/87 testcases\nstep-1 sort the ds\n step-2: Solve it like LIS problem (https://leetcode.com/problems/longest-increasing-s
**Approach-1:** O(N^2) Approach | passed 85/87 testcases\nstep-1 sort the ds\n step-2: Solve it like LIS problem (https://leetcode.com/problems/longest-increasing-subsequence/discuss/2072338/c-on2-solution-explained-through-comments) \n\n```\nclass Solution {\npublic:\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        //step-1: sort the envelopes in increasing order\n        sort(envelopes.begin(), envelopes.end());\n        \n        int n = envelopes.size(), mx = 1; //1 envelope will be there always\n        \n        vector<int> LIS(n, 1);  //1 for a single envelop\n        \n        //step-2: find LIS(Longest Increasing Sequence)\n        for(int i=1;i<n; i++){\n            for(int j=0; j<i; j++){\n                if(envelopes[i][0]> envelopes[j][0] && envelopes[i][1]> envelopes[j][1] && LIS[i]<=LIS[j])\n                   LIS[i] = 1+ LIS[j];\n            }\n            mx = max(mx, LIS[i]);\n        }\n        \n        return mx;\n    }\n};\n```\n\n**Approach-2:** O(NlogN) Approach\n```\nclass Solution {\n    static bool cmp(vector<int>& a, vector<int>& b){\n        if(a[0]==b[0]) return a[1] > b[1];\n        return a[0] < b[0];\n    }\npublic:\n    int maxEnvelopes(vector<vector<int>>& env) {\n        int n = env.size();\n        \n        // sorting by height & if we encounter same height\n        // sort by descending order of width\n        sort(env.begin(), env.end(), cmp);\n        \n      \n        vector<int> lis;\n        \n        for(int i = 0;i<env.size();i++){\n            int ele = env[i][1];\n            \n            int idx = lower_bound(lis.begin(), lis.end(), ele) - lis.begin();\n            \n            if(idx >= lis.size()) lis.push_back(ele);\n            else lis[idx] = ele;\n        }\n        \n        return lis.size();\n    }\n};\n```
['C']