LIS | O(NlogN) | Easy to understand | Intuitive
Longest Increasing Subsequence in 2 dimension!\nFirstly, if you have solved the Longest Increasing Subsequence (LIS) question, you\'ve perhaps related this ques
# Longest Increasing Subsequence in 2 dimension!\nFirstly, if you have solved the `Longest Increasing Subsequence (LIS)` question, you\'ve perhaps related this question to LIS in some way or the other, if so, you\'re in the right track. In LIS we found the longest increasing subsequence in an 1D array but in this question the ask is to find the LIS in 2D array *(for both the width and the height, since an envelope can get inside another envelope iff both its height and width are smaller than the other one)*. The trick is to **sort the array according to its width**. That makes life easier as now we only need to deal with the height since width is already sorted. So **the LIS of height will automatically be the LIS of both width and height**.\n\n**Input:** ```[[5,4],[6,4],[6,7],[2,3]]```\n**After sorting:** ```[[2,3],[5,4],[6,7],[6,4]]```\nNow an LIS on height i.e., ```[3,4,7,4]``` will give 3 as the length since ```[3,4,7]``` is the LIS.\nAnd now if you bring the width into the picture ```[[2,3],[5,4],[6,7]]``` is the LIS of both width and height, which means an envelope ```[2,3]``` can be put inside an envelope ```[5,4]``` which in turn can be put inside an envelope ```[6,7]```. Hope the requirement of the concept of LIS is no more a question here.\n\nWe need to take care of certain scenarios where width may be same for 2 or more envelopes, say, `[6,5]` & `[6,7]`. In such scenarios we can not take both `5` and `7` in our LIS *(of height)* since the envelope of same width can not get inside the other. To skip this scenario and only take one envelope we better configure our code to sort the height in reverse order only when 2 or more width of envelopes are same. Now in the sorted array, `[6,7]` will appear before `[6,5]` so the LIS of height won\'t take both `7` & `5` into calculation.\n\n**Code:**\n```\nclass Solution {\npublic:\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        int N = envelopes.size();\n        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b) {\n            if(a[0]==b[0]) return a[1]>b[1];\n            return a[0]<b[0];\n        });\n        // for(int i=0; i<N; i++) cout<<envelopes[i][0]<<" "<<envelopes[i][1]<<endl;\n        vector<int> dp;\n        dp.push_back(envelopes[0][1]);\n        int l=1;\n        for(int i=1; i<N; i++) {\n            if(envelopes[i][1]>dp.back()) {\n                dp.push_back(envelopes[i][1]);\n                l++;\n            }\n            else {\n                int index = lower_bound(dp.begin(), dp.end(), envelopes[i][1]) - dp.begin();\n                dp[index] = envelopes[i][1];\n            }\n        }\n        return l;\n    }\n};\n```\n**Time complexity:** `O(NlogN)` *(for sorting)* + `O(NlogN)` *(for inserting into the DP vector * for finding the lower bound)* ~ `O(NlogN)`\n**Space complexity:** `O(N)` *(size of the DP vector)*\n\nDo hit a like if you like the explanation. Thank you.
['Dynamic Programming', 'C', 'Binary Tree']