JAVA || LIS Application
Explanation:\nBasically its an 2-D version of longest-increasing-subsequence and there is a 3-D version also which is very popular interview problem of Codenati
**Explanation:**\nBasically its an 2-D version of [longest-increasing-subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) and there is a 3-D version also which is very popular interview problem of Codenation and Google [Box-stacking] .\n\nNote: `One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.`\neg : envelope = [[5,4],[6,4],[6,7],[2,3]]\nAfter sorting\n```\n\n2   5   6   6\n3   4   7   4\n[6,7] is placed before [6,4] because if we select 7 we have to discard 4 as they both have width same.\n```\n**Approch 1: Comparable Based**\n**CODE:**\n```\nclass Solution {\n    public int maxEnvelopes(int[][] envelopes) {\n        Pair[] arr=new Pair[envelopes.length];\n        for(int i=0;i<arr.length;i++){\n            int[] nums=envelopes[i];\n            int w=nums[0];\n            int h=nums[1];\n            Pair np=new Pair(w,h);\n            arr[i]=np;\n        }\n          Arrays.sort(arr);\n       \n         return LIS(arr);\n    }\n    \n    private int LIS(Pair[] arr){\n          int ans=0;\n          int[] minele=new int[arr.length];\n        for(int i=0;i<arr.length;i++){\n            int val=arr[i].h;\n            int lo=0, hi=ans;\n            \n            while(lo<hi){\n                int mid=(lo + hi)/2;\n                if(minele[mid]<val){\n                    lo=mid+1;\n                }else{\n                    hi=mid;\n                }\n            }\n            minele[lo]=val;\n            \n            if(lo==ans){\n                ans++;\n            }\n        }\n        return ans;\n    }\n    \n    public static class Pair implements Comparable<Pair>{\n        int w;\n        int h;\n        \n        Pair(int w,int h){\n            this.w=w;\n            this.h=h;\n        }\n        \n        @Override\n        public int compareTo(Pair other){\n            if(this.w==other.w) return other.h -this.h;\n            return this.w-other.w;\n        }\n    }\n}\n```\n**Complexity :**\n`Time : O(nlogn) and Space:O(n)`\n\n**Approch2 : Comparator Based\nCODE:**\n```\nclass Solution {\n    public int maxEnvelopes(int[][] envelopes) {\n         Arrays.sort(envelopes,new EnvelopeComparator());\n         return LIS(envelopes);\n    }\n    \n    private int LIS(int[][] arr){\n          int ans=0;\n          int[] minele=new int[arr.length];\n        for(int i=0;i<arr.length;i++){\n            int val=arr[i][1];\n            int lo=0, hi=ans;\n            \n            while(lo<hi){\n                int mid=(lo + hi)/2;\n                if(minele[mid]<val){\n                    lo=mid+1;\n                }else{\n                    hi=mid;\n                }\n            }\n            minele[lo]=val;\n            \n            if(lo==ans){\n                ans++;\n            }\n        }\n        return ans;\n    }\n    \n    public class EnvelopeComparator implements Comparator<int[]>{\n        @Override\n        public int compare(int[] one,int[] two){\n            if(one[0]==two[0]) return two[1]-one[1];\n            return one[0]-two[0];\n        }\n    }\n}\n```\n**COMPLEXITY:** `TIME:O(NLOGN) AND SPACE:O(N)(minele array space)`\n\nPlease **UPVOTE** if found it helpful and feel free to reach out to me or comment down if you have any doubt.\n\n
['Dynamic Programming', 'Binary Tree', 'Java']