Most Detailed and BEGINNER FRIENDLY Explanation || Binary Search and DP (Memoization)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nv = [[5,4],[6,4],[6,7],
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nv = [[5,4],[6,4],[6,7],[2,3]]\n\nSort this vector in increasing order wrt to the first element.\nIf v[i].first == v[i + 1].first, in this case sort in decreasing order wrt to the second element.\n\nv = [[2,3],[5,4],[6,7],[6,4]]\n\nWhy we are sorting the vector pair like this?\n\nNotice it carefully, after sorting it like this, it **reduces to a very famous problem called Longest Increasing Subsequence**, wrt to second part of the vector array.\n\nNow you have to just ignore the first element i.e. v[i].first and solve the problem wrt to v[i].second and it is same as **Longest Increasing Subsequence**.\n\nI am attaching the problem here, for your reference.\n\n[Longest Increasing Subsequence](https://leetcode.com/submissions/detail/997895245/)\n\n\n# **Note**: \n**Recursion with Memoization won\'t work here due to constraints of the problem.**\n\nRecursion with Memoization will give **TLE**.\n\n1 <= envelopes.length <= 10^5\n\nBut still **here is the code of  RECURSION with MEMOIZATION** for your better understanding.\n\n```\nclass Solution {\npublic:\n    static bool sortbyCond(const pair<int, int>& a, const pair<int, int> &b)\n    {\n        if(a.first != b.first) return (a.first < b.first);\n        else return (a.second > b.second);\n    }\n\n    int solveMem(vector<pair<int, int>> &nums, int curr, int prev, vector<vector<int>> &dp)\n    {\n        if(curr == nums.size()) return 0;\n        if(dp[curr][prev + 1] != -1) return dp[curr][prev + 1];\n\n        int inc = 0, exc = 0;\n\n        if(prev == -1 || nums[prev].second < nums[curr].second)\n        {\n            inc = 1 + solveMem(nums, curr + 1, curr, dp);\n        }\n        exc = 0 + solveMem(nums, curr + 1, prev, dp);\n\n        dp[curr][prev + 1] = max(inc, exc);\n\n        return dp[curr][prev + 1];\n    }\n    \n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        vector<pair<int,int>> v;\n        for(int i = 0; i < envelopes.size(); i++)\n        {\n            v.push_back({envelopes[i][0], envelopes[i][1]});\n        }\n\n        sort(v.begin(), v.end(), sortbyCond);\n\n        vector<vector<int>> dp(v.size(), vector<int> (v.size(), -1));\n\n        return solveMem(v, 0, -1, dp);\n    }\n};\n```\n\n---\n\n# Now coming to the main solution of this problem:\n\nSo the idea here is to apply the **binary search** on the sorted array.\n\n**v = [[2,3],[5,4],[6,7],[6,4]]**\n\nFor simplicity treat the problem as Longest Increasing Subsequence on second part of the vector v, as our problem as reduced to this only.\n\nNow I\'ll take a better example to explain the binary search solution:\n**nums = [5,8,3,7,9,1]**\n\n1st iteration: LIS = [5]\n2nd iteration: LIS = [5,8]\n3rd iteration: LIS = [5,8] , [3]\n4th iteration: LIS = [5,8] , [3,7]\n5th iteration: LIS = [5,8,9] , [3,7,9]\n6th iteration: LIS = [5,8,9], [3,7,9]\n\nBut after reading the problem carefully we come to know that we just want the length of the Longest Increasing Subsequence and the order just doesn\'t matter.\n\nSo, now push the first element to the ans vector and after each iteration compare the last element of the answer vector to the next element of the vector nums and\n\nif(nums[i].second > ans.back()){\nans.push_back(nums[i].second);\n}\nelse{\nint index = lower_bound(ans.begin(), ans.end(), nums[i].second) - ans.begin();\nans[index] = nums[i].second;\n}\n\n**Dry Run:**\n**nums = [5,8,3,7,9,1]**\n\n1st iteration: ans = [5]\n2nd iteration: ans = [5,8]\n3rd iteration: ans = [3,8]\n4th iteration: ans = [3,7]\n5th iteration: ans = [3,7,9]\n6th iteration: ans = [1,7,9]\n\n**ans.size() = 3** \nwhich is our required ans.\n\n\n### Feel free to post your doubts in the comment section.\n\n# Complexity\n- Time complexity: **O(n logn)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(n)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    static bool sortbyCond(const pair<int, int>& a, const pair<int, int> &b)\n    {\n        if(a.first != b.first) return (a.first < b.first);\n        else return (a.second > b.second);\n    }\n\n    int solveOptimal(vector<pair<int, int>> &nums)\n    {\n        if(nums.size() == 0) return 0;\n        vector<int> ans;\n        ans.push_back(nums[0].second);\n\n        for(int i = 1; i < nums.size(); i++)\n        {\n            if(nums[i].second > ans.back())\n            {\n                ans.push_back(nums[i].second);\n            }\n            else\n            {\n                int index = lower_bound(ans.begin(), ans.end(), nums[i].second) - ans.begin();\n                ans[index] = nums[i].second;\n            }\n        }\n        return ans.size();\n    }\n\n    \n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        vector<pair<int,int>> v;\n        for(int i = 0; i < envelopes.size(); i++)\n        {\n            v.push_back({envelopes[i][0], envelopes[i][1]});\n        }\n\n        sort(v.begin(), v.end(), sortbyCond);\n\n        return solveOptimal(v);\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']