Python [Reduce to 1D]
Reduce the problem to 1D and then it becomes Leetcode Problem 300 - Longest Increasing Subsequence.\nOnce the letters are sorted in increasing width, we only ne
Reduce the problem to 1D and then it becomes Leetcode Problem 300 - Longest Increasing Subsequence.\nOnce the letters are sorted in increasing width, we only need to sort based on height. Same width envelopes can be traversed in decreasing height because they will never be included in the same sequence.\n\nIf all the letter widths are distinct it would be much easier to see that this is Longest Increasing Subsequence.\n\nBut the reduction in this case is not trivial. Even if you find it, you need the binary search solution for Longest Increasing Subsequence, that one is not trivial either. In fact, I found this question to be one of the hardest.\n\nAlso the "vanilla" DP would work perfectly fine for sequences of smaller length (typically less than 1000 on Leetcode platform), which is `O(N^2)`.\n\nTime: `O(N logN)` due to sort and longest increasing subsequence computation\nSpace: `O(N)`\n\n\n```python\nclass Solution:\n    def maxEnvelopes(self, A):\n        #sort A\n        A.sort(key = lambda x: (x[0], -x[1]))\n        #reduce to 1D\n        A1 = [y for _,y in A]\n        #Now this is Leetcode 300\n        return self.lengthOfLIS(A1)\n                \n    #Leetcode 300\n    def lengthOfLIS(self, A1):\n        L = 0\n        DP = []\n        for x in A1:\n            i = bisect.bisect_left(DP, x)\n            if i == len(DP):\n                DP.append(x)\n            else:\n                DP[i] = x\n            if i == L:\n                L += 1\n        return L     \n```
[]