4 APPROCH WITH EXPLAIN->SAME AS LIS
Intuition\n Describe your first thoughts on how to solve this problem. \nLONGEST INCREASING SUBSEQUENCE SAME\n# Approach\n Describe your approach to solving the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLONGEST INCREASING SUBSEQUENCE SAME\n# Approach\n<!-- Describe your approach to solving the problem. -->\nRussian dolls hai unko envelops me dalna hai to sort kardia width wise but agar width same hui kisi ki toh kya kre?\n\nto hmne HIEGHT ko sort krdia but descending order me an descending order me kyu kara ?\nbeacuse hum LIS lga sake uspr agar hum normal karenge to mja n aaega..\n(Complex hoega)\n\n#love babar bhaiya\n\n# Complexity\n- Time complexity:RECURSION->exponential (TLE)\n- MEMOIZATION-> O(N*N) (TLE)\n- TOP-DOWN-> O(N*N) (TLE)\n- Binary search ->O(N*LOG(N)) (optimised)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- MEMOIZATION-> O(N*N)\n- TOP-DOWN-> O(N*N)\n- Binary search ->O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n   \n    // int solve(int n, vector<vector<int>>& envelopes,int curr,int prev)\n    // {\n    //     if(curr == n)\n    //     {\n    //         return 0;\n    //     }\n\n    //     int include=0;\n    //     if(prev == -1 or (envelopes[prev][0] < envelopes[curr][0] and \n    //     envelopes[prev][1] < envelopes[curr][1]))\n    //     {\n             //check with and heigth both\n    //         include = 1 + solve(n,envelopes,curr+1,curr);\n    //     }\n\n    //     int exclude = 0 + solve(n,envelopes, curr+1, prev);\n\n    //     return max(include,exclude);\n    // }\n\n    // int solve_mem(int n, vector<vector<int>>& envelopes,int curr,int prev,vector<vector<int>> &dp)\n    // {\n    //     if(curr == n)\n    //     {\n    //         return 0;\n    //     }\n\n    //     if(dp[curr][prev+1] != -1)\n    //     return dp[curr][prev+1];\n\n\n    //     int include=0;\n    //     if(prev == -1 or (envelopes[prev][0] < envelopes[curr][0] and \n    //     envelopes[prev][1] < envelopes[curr][1]))\n    //     {\n    //         include = 1 + solve_mem(n,envelopes,curr+1,curr,dp);\n    //     }\n\n    //     int exclude = 0 + solve_mem(n,envelopes, curr+1, prev,dp);\n\n    //     dp[curr][prev+1] = max(include,exclude);\n\n    //     return dp[curr][prev+1];\n    // }\n\n    static bool comp(const vector<int> &v1,const vector<int> &v2)\n    {\n        if(v1[0] == v2[0])\n        {\n            return v1[1] > v2[1];\n        }\n        else\n        return v2[0] > v1[0];\n    }\n\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n\n\n        // sort(envelopes.begin(),envelopes.end());\n\n        //   for(int i=0;i<envelopes.size();i++)\n        //   {\n        //       for(int j=0;j<envelopes[0].size();j++)\n        //       {\n        //           cout<<"envelopes[i][j]"<<envelopes[i][j]<<" ";\n        //       }\n        //       cout<<endl;\n        //   }\n\n        //RECURSION\n        // return solve(envelopes.size(), envelopes, 0, -1);\n        \n        //MEMOIZATION\n        // vector<vector<int>> dp(envelopes.size()+1,vector<int>(envelopes.size()+1,-1));\n        // return solve_mem(envelopes.size(), envelopes, 0, -1,dp);\n\n        //TABULATION\n\n        // vector<vector<int>> dp(envelopes.size()+1,vector<int>(envelopes.size()+1,0));\n        // int n=envelopes.size();\n        // for(int curr = n-1; curr>=0; curr--)\n        // {\n        //     for(int prev= curr-1; prev>=-1; prev--)\n        //     {\n        //             int include=0;\n        //             if(prev == -1 or (envelopes[prev][0] < envelopes[curr][0] and \n        //             envelopes[prev][1] < envelopes[curr][1]))\n        //             {\n        //                 include = 1 + dp[curr+1][curr+1];\n        //             }\n\n        //             int exclude = 0 + dp[curr+1][prev+1];\n\n        //             dp[curr][prev+1] = max(include,exclude);\n        //     }\n        // }\n\n        // return dp[0][0];\n\n        //BINARY SEARCH\n\n    //      \n      int n = envelopes.size();\n        sort(envelopes.begin(),envelopes.end(),comp);\n        vector<int>arr;\n        for(int i =0;i<n;i++)\n        {\n            if(arr.empty() || arr.back()<envelopes[i][1])\n                arr.push_back(envelopes[i][1]);\n            else\n            {\n                int index = lower_bound(arr.begin(),arr.end(),envelopes[i][1])\n                        -   arr.begin();\n                arr[index] = envelopes[i][1];\n            }\n        }\n        \n        return arr.size();\n    }\n};\n\n\n// class Solution {\n// public:\n//     static bool cmp(const vector<int>& v1, const vector<int>& v2)\n//     {\n//       if(v1[0] == v2[0]) return v1[1] > v2[1];\n//             return v1[0]<v2[0];\n//     }\n//     int maxEnvelopes(vector<vector<int>>& envelopes) {\n//         int n = envelopes.size();\n//         sort(envelopes.begin(),envelopes.end(),cmp);\n//         vector<int>arr;\n//         for(int i =0;i<n;i++)\n//         {\n//             if(arr.empty() || arr.back()<envelopes[i][1])\n//                 arr.push_back(envelopes[i][1]);\n//             else\n//             {\n//                 int index = lower_bound(arr.begin(),arr.end(),envelopes[i][1])\n//                         -   arr.begin();\n//                 arr[index] = envelopes[i][1];\n//             }\n//         }\n        \n//         return arr.size();\n//     }\n// };\n\n```
['C++']