Binary Search (T.C=O(nlogn),S.C=O(n)) Approach || Beats 98%
\n\n# Approach: \n Describe your approach to solving the problem. \n1. Sorting:\n\n- First, sort the envelopes by their width in ascending order. If two envelop
\n\n# Approach: \n<!-- Describe your approach to solving the problem. -->\n1. Sorting:\n\n- First, sort the envelopes by their width in ascending order. If two envelopes have the same width, sort them by height in descending order. This ensures that when processing envelopes with the same width, you only consider the heights to maintain a strictly increasing sequence of heights.\n2. Finding Longest Increasing Subsequence (LIS):\n\n- After sorting, the problem reduces to finding the Longest Increasing Subsequence (LIS) based on the heights of the envelopes. This is because the widths are already sorted, so you only need to focus on the heights to find the maximum nesting.\n\n3. Binary Search:\n\n- Use a dynamic array ans to keep track of the smallest possible ending height of increasing subsequences of different lengths. For each envelope, use binary search to determine the position where the current height fits into this array, updating the array as needed. This ensures that the ans array always maintains the smallest possible values at each length, which helps in achieving the LIS efficiently.\n\n# Complexity\n- Time complexity: O(nlogn)\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 {\nprivate:\nstatic bool cmp(vector<int> &a, vector<int> &b)\n    {\n        // If the widths are equal, sort in descending order of heights\n        if (a[0] == b[0])\n        {\n            return a[1] > b[1];\n        }\n\n        // Sort in ascending order of widths\n        return a[0] < b[0];\n    }\n\nint solveBS(int n,vector<vector<int>>& nums)\n    {\n            sort(nums.begin(),nums.end(),cmp);\n\n            vector<int> ans;\n            ans.push_back(nums[0][1]);\n\n            for(int i=1;i<n;i++)\n            {\n                if(nums[i][1]>ans.back()) ans.push_back(nums[i][1]);\n                else\n                {\n                    //find index of just bada element in ans\n                    int index=lower_bound(ans.begin(),ans.end(),nums[i][1])-ans.begin();\n                    ans[index]=nums[i][1];\n                }\n            }\n\n            return ans.size();\n    }       \npublic:\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        int n=envelopes.size();\n        return solveBS(n,envelopes);      \n    }\n};\n```\n\n![upvote.jpg](https://assets.leetcode.com/users/images/adaddc7d-db64-4dbc-81b3-140bb869bed8_1723150268.7509692.jpeg)\n
['Binary Search', 'Sorting', 'C++']