Russian Doll Envelopes || O(NlogN) || LIS || Binary Search
First, we sort the Envelopes. width in ascending order and height in decending order. Then apply LIS (Longest Increasing Subsequence) on height to find the requ
First, we sort the Envelopes. width in ascending order and height in decending order. Then apply LIS (Longest Increasing Subsequence) on height to find the required length.\n\nWhy height in decending order?\nIf we sort the height in ascending order and If the width of two envelopes are same and the height of first envelope is less than the next envelope, there will be LIS of 2 length but first envelope can not fit in next envelope because the width of both envelopes are same.\nExample: If sort both width and height in ascending order : [6,4],[6,7]. Here LIS will be [4,7], lenght will be 2 but they can not fit.\nIf sort width in ascending order and height in decending order : [6,7],[6,4]. Here LIS will be either [7] or [4], length will be 1 because they can not fit.\n\nIf width of some envelopes are same, they can not fit. Here We apply the LIS with respect to height, we sort the height in decending order so that the envelopes with same width can not be in one LIS.\n\n\nHere we will use binary search to find the length of LIS. Binary Search approach can only find the length of LIS but not the elements of LIS.\nLet\'s create a list lis to store the LIS. It may not be valid LIS but length will be correct.\n\nSuppose a new element come, find the index where it can fit in lis so that lis will be in increasing subsequence. If it can not fit in lis, append in the lis.\n\nExample: [1,7,8,4,5,6,-1,9]\nlis : []\n(i)   element 1 : lis -> [1]\n(ii)  element 7 : lis -> [1,7]\n(iii) element 8 : lis -> [1,7,8]\n(iv)  element 4 : lis -> [1,4,8]  4 fit at place of 7. Now suppose two or more elements new element come greater than 4 but less tha equal to 7 in increasing sequence (e.g. [5,6,7]), we can find a larger subsequence([1,4,5,6,7]) than the previous subsequence ([1,7,8])\n(v)   element 5 : lis -> [1,4,5] 5 can fit at place of 8. You can think that a new element come that can be in increasing sequence with 8 element (e.g. 10) but That element also will be in increasing subsequence with lesser element than 8 elemnt (e.g. 5).\n(vi)  element 6 : lis -> [1,4,5,6]\n(vii) element -1: lis -> [-1,4,5,6]\n(viii)element 9 : lis -> [-1,4,5,6,9]\n\nThis is not the valid LIS ([-1,4,5,6,9]) but length of the longest valid subsequence will be equal to this LIS.\nIn a valid subsequence element at a index will be greater than or equal to the element at that index in this LIS.\n\nHere we will use binary search to find the position of new element where it can fit in the lis.\n\nCollections.binarySearch(List<T>, T) return the index of the element in the list if it is present in the list.\nIf it is not present in the list, it will return  -(insertion index)-1 or -(insertion index+1).\nIf it is negative, multiply by -1 and then subtract 1 from it to find the correct position in lis.\n\nclass Solution {\n    \n    List<Integer> lis;\n    public int maxEnvelopes(int[][] envelopes) {\n        \n        Arrays.sort(envelopes, (a, b)-> a[0]==b[0] ? b[1]-a[1] : a[0]-b[0]); //sort width in asending order and height in desending order.\n        \n        lis = new ArrayList<>();\n        \n        lis.add(envelopes[0][1]);\n        \n        for(int k=1; k<envelopes.length; k++){\n            \n            if(lis.get(lis.size()-1) < envelopes[k][1]) lis.add(envelopes[k][1]);\n            else lis.set(binarySearch(envelopes[k][1]), envelopes[k][1]);\n        }\n        \n        return lis.size();\n    }\n    \n    int binarySearch(int height){\n        \n        int i = Collections.binarySearch(lis, height);\n        if(i < 0){\n            \n            i *= -1;\n            i -= 1;\n        }\n        return i;\n        \n        /*int low = 0, high = lis.size()-1, mid, pos = 0;\n        \n        while(low <= high){\n            \n            mid = (low + high)/2;\n            if(lis.get(mid) == height) return mid;\n            if(lis.get(mid) < height){\n                \n                pos = mid+1;\n                low = mid+1;\n            }\n            else high = mid-1;\n        }\n        return pos;*/\n    }\n}
['Binary Tree', 'Java']