Easy || Relatable approach|| learn from 300.
Intuition\n Describe your first thoughts on how to solve this problem. \nSee this problem is similar to 300. Longest Increasing Subsequence , I have explained i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSee this problem is similar to 300. Longest Increasing Subsequence , I have explained in detailed how patience sort works read it here https://leetcode.com/problems/longest-increasing-subsequence/solutions/4514634/easy-patience-sorting-o-nlogn/\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the array. Ascend on width and descend on height if width are same.\nFind the longest increasing subsequence based on height of envelopea.\nAs you have arranges the height in decreasing sense for same width the code will automatically choose the least height for consideration ( read the link above).\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlogN)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int maxEnvelopes(int[][] envelopes) {\n    Arrays.sort(envelopes, (a, b) -> {\n        if (a[0] == b[0]) {\n            return b[1] - a[1];\n        }\n        else {\n            return a[0] - b[0];\n        }\n    });\n    int nums[]=new int [envelopes.length];\n    int j=0;\n    for(int i=0;i<envelopes.length;i++){\n        nums[j]=envelopes[i][1];\n        j++;\n    }\n    return lengthOfLIS(nums);\n    }\n// the below part is taken exact from problem 300 , read the link above.\n\n    public int lengthOfLIS(int[] nums) {\n        ArrayList<Integer> al=new ArrayList<>();\n        for(int i=0;i<nums.length;i++){\n            int index=binary(al,nums[i]);\n            if(index==al.size()){\n                al.add(nums[i]);\n            }\n            else{\n                al.set(index,nums[i]);\n            }\n            \n        }\n        return al.size();\n    }\n\n\n    public int binary(ArrayList<Integer> al,int target){\n        int s=0;\n        int e=al.size();\n        int result=al.size();\n        while(s<e){\n            int mid=(s+e)/2;\n            if(al.get(mid)<target){\n                s=mid+1;\n            }\n            else{\n                e=mid;\n                result=mid;\n            }\n        }\n        return result;\n    }\n}    \n\n```
['Java']