✅C++ || Recursion->Memoization->BinarySearch
Method -1 [Recursion] Gives TLE!\n\n\n\tclass Solution {\n\tpublic:\n\t//     LIS\n\t\tint f(int i,int prev,vector>& env,int n){\n\t\t\tif(i==n) return 0;\n\t\t
# Method -1 [Recursion] Gives TLE!\n![image](https://assets.leetcode.com/users/images/1530a62f-ec33-4ff3-8bbb-4b3299483ad7_1662447073.3290262.png)\n\n\tclass Solution {\n\tpublic:\n\t//     LIS\n\t\tint f(int i,int prev,vector<vector<int>>& env,int n){\n\t\t\tif(i==n) return 0;\n\t\t\tint pick=INT_MIN;\n\t\t\tif(prev==-1 || env[prev][0]<env[i][0] && env[prev][1]<env[i][1]) pick=1+f(i+1,i,env,n);\n\t\t\tint notpick=f(i+1,prev,env,n);\n\t\t\treturn max(pick,notpick);\n\t\t}\n\n\t\tint maxEnvelopes(vector<vector<int>>& env) {\n\t\t\tint n=env.size();\n\t\t\tsort(env.begin(),env.end());   \n\t\t\treturn f(0,-1,env,n);\n\t\t}\n\t};\n\n# Method - 2 [Memoization] Gives TLE!!\n![image](https://assets.leetcode.com/users/images/cbe4275e-10a2-461d-8b6f-078ffc8d3284_1662447245.8835037.png)\n\n\tclass Solution {\n\tpublic:\n\t//     LIS\n\t\tint f(int i,int prev,vector<vector<int>>& env,int n,vector<vector<int>>& dp){\n\t\t\tif(i==n) return 0;\n\t\t\tif(dp[i][prev+1]!=-1) return dp[i][prev+1];\n\t\t\tint pick=INT_MIN;\n\t\t\tif(prev==-1 || (env[prev][0]<env[i][0] && env[prev][1]<env[i][1])) pick=1+f(i+1,i,env,n,dp);\n\t\t\tint notpick=f(i+1,prev,env,n,dp);\n\t\t\treturn dp[i][prev+1]=max(pick,notpick);\n\t\t}\n\n\t\tint maxEnvelopes(vector<vector<int>>& env) {\n\t\t\tint n=env.size();\n\t\t\tsort(env.begin(),env.end());   \n\t\t\tvector<vector<int>> dp(n,vector<int>(n+1,-1));\n\t\t\treturn f(0,-1,env,n,dp);\n\t\t}\n\t};\t\n\t\n***Since we can not reduce the TC further by Tabulation thus we have to apply Binary Search!**\n\n# Method - 3 [Binary Search] \n\n![image](https://assets.leetcode.com/users/images/d1dbbf1d-cc0b-49c7-891f-7a60981db60d_1662447269.8608131.png)\n\n\n**T->O(nlogn) && S->O(n)**\n\n\tclass Solution {\n\tpublic:\n\t\tstatic bool comp(vector<int>& a,vector<int>& b){\n\t\t\tif(a[0]==b[0]) return a[1]>b[1];\n\t\t\treturn a[0]<b[0];\n\t\t}\n\n\t\tint maxEnvelopes(vector<vector<int>>& env) {\n\t\t\tint n=env.size();\n\t\t\tsort(env.begin(),env.end(),comp);   \n\t\t\tvector<int> temp;\n\t\t\ttemp.push_back(env[0][1]);\n\t\t\tfor(int i=1;i<n;i++){\n\t\t\t\tif(temp.back()<env[i][1]) temp.push_back(env[i][1]);\n\t\t\t\telse{\n\t\t\t\t\tint ind=lower_bound(temp.begin(),temp.end(),env[i][1])-temp.begin();\n\t\t\t\t\ttemp[ind]=env[i][1];\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn temp.size();\n\t\t}\n\t};\n
['Binary Search', 'Recursion', 'Memoization', 'C', 'Sorting', 'C++']