JS, Python, Java, C++ | Easy LIS Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nThe naive approach here would be to try every single permutation of our envelope array (**E**), but that would be a **time complexity** of **O(N!)** which is frankly an incomprehensible number when **N** goes up to **5000**.\n\nAs the naive approach would involve repeating many of the same individual comparisons over and over again, we can quickly see that a **dynamic programming** (**DP**) solution would be beneficial.\n\nIn order for a DP solution to be effective, however, we\'d need to find a way to progress from the easiest subsolution and build from there for each successively more complex subsolution. The best way to do this would be to sort **E** first by **width** (**E[i][0]**), and then by **height** (**E[i][1]**).\n\nThen we could start with the smallest envelope and work our way up, storing in our DP array (**dp**) the result of how many smaller envelopes it is possible to fit in the corresponding envelope. That way we could simplify each iteration to checking to see which of the entries in **dp** corresponding to smaller envelopes is the largest. This would drop the time complexity to **O(N^2)**, which is a definite improvement.\n\nBut it should also be apparent that if we were to define a **subsequence** of **E** that was the ideal nesting order of envelopes for the solution, then that array would be strictly increasing in *both* width and height.\n\nIf we\'ve already sorted **E** primarily by width, we should then be able to consider a corresponding array of just the heights and realize that the solution would be defined as the [**longest increasing subsequence**](https://en.wikipedia.org/wiki/Longest_increasing_subsequence) of that.\n\nThe only difficulty would be for consecutive envelopes with the *same* sorted width. To avoid that, we can simply make sure that our sort function sorts height in descending order so that the first envelope encountered for any given width would be the largest one.\n\nAt the end of the longest increasing subsequence algorithm, the length of **dp** is equal to the length of the subsequence. Due to the sort function and the binary searches required for the algorithm, the time complexity now shrinks to **O(N log N)**.\n\n---\n\n#### ***Implementation:***\n\nPython has a built-in binary search function, **bisect()**.\n\nJava has a built-in binary search function as well (**Arrays.binarySearch()**), but in order to use the more performant **int[]** rather than a **List< Integer >**, we\'ll need to specify a max length for **dp** and then keep track of the current index of the longest subsequence separately in **ans**.\n\nC++ has a built-in binary search function, **lower_bound()**.\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **80ms / 40.8MB** (beats 100% / 90%).\n```javascript\nvar maxEnvelopes = function(E) {\n    E.sort((a,b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0])\n    let len = E.length, dp = []\n    for (let i = 0; i < len; i++) {\n        let height = E[i][1], left = 0, right = dp.length   \n        while (left < right) {\n            let mid = (left + right) >> 1\n            if (dp[mid] < height) left = mid + 1\n            else right = mid\n        }\n        dp[left] = height\n    }\n    return dp.length\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **140ms / 16.4MB** (beats 97% / 85%).\n```python\nclass Solution:\n    def maxEnvelopes(self, E: List[List[int]]) -> int:\n        E.sort(key=lambda x: (x[0], -x[1]))\n        dp = []\n        for _,height in E:\n            left = bisect_left(dp, height)\n            if left == len(dp): dp.append(height)\n            else: dp[left] = height\n        return len(dp)\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **7ms / 39.5MB** (beats 100% / 95%).\n```java\nclass Solution {\n    public int maxEnvelopes(int[][] E) {\n        Arrays.sort(E, (a,b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);\n        int[] dp = new int[E.length];\n        int ans = 0;\n        for (int[] env : E) {\n            int height = env[1];\n            int left = Arrays.binarySearch(dp, 0, ans, height);\n            if (left < 0) left = -left - 1;\n            if (left == ans) ans++;\n            dp[left] = height;\n        }\n        return ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **32ms / 15.9MB** (beats 99% / 99%).\n```c++\nclass Solution {\npublic:\n    int maxEnvelopes(vector<vector<int>>& E) {\n        sort(E.begin(), E.end(), [](vector<int>& a, vector<int>& b) \n             -> bool {return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];});\n        vector<int> dp;\n        for (auto& env : E) {\n            int height = env[1];\n            int left = lower_bound(dp.begin(), dp.end(), height) - dp.begin();\n            if (left == dp.size()) dp.push_back(height);\n            dp[left] = height;\n        }\n        return dp.size();\n    }\n};\n```
['C', 'Python', 'Java', 'JavaScript']