No DP| Using Binary Search & LIS| CPP| Java| C| Python| Intuition| Approach
Intuition\nThe problem of Russian doll envelopes is a variation of the longest increasing subsequence problem (LIS). The goal is to find the largest set of enve
# Intuition\nThe problem of Russian doll envelopes is a variation of the longest increasing subsequence problem (LIS). The goal is to find the largest set of envelopes such that each envelope can fit into the next one in the set. To do this, we need to sort the envelopes and then find the LIS based on their dimensions.\n\n# Approach\n1. Sort the Envelopes: First, sort the envelopes by their width in ascending order. If two envelopes have the same width, sort them by height in descending order. Sorting by height in descending order for equal widths ensures that we don\'t consider envelopes with the same width but different heights as a valid sequence in the LIS step.\n\n2. Extract Heights: After sorting, extract the heights of the envelopes into a separate list.\n\n3. Longest Increasing Subsequence (LIS): Apply the LIS algorithm on the heights list. The LIS will give the maximum number of envelopes you can Russian doll.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# CPP Code\n```\nclass Solution {\npublic:\n    int maxEnvelopes(std::vector<std::vector<int>>& envelopes) {\n        // Sort envelopes by width in ascending order. \n        // If two envelopes have the same width, sort by height in descending order.\n        std::sort(envelopes.begin(), envelopes.end(), [](const std::vector<int>& a, const std::vector<int>& b) {\n            if (a[0] == b[0]) return a[1] > b[1];\n            return a[0] < b[0];\n        });\n\n        // Extract the heights into a separate list.\n        std::vector<int> heights;\n        for (const auto& envelope : envelopes) {\n            heights.push_back(envelope[1]);\n        }\n\n        // The \'ans\' vector will store the increasing subsequence of heights.\n        std::vector<int> ans;\n\n        for (const int height : heights) {\n            // Find the position where \'height\' can be placed in \'ans\' using binary search.\n            auto it = std::lower_bound(ans.begin(), ans.end(), height);\n\n            // If \'height\' is greater than all elements in \'ans\', append it.\n            if (it == ans.end()) {\n                ans.push_back(height);\n            } \n            // Otherwise, replace the element at the found position with \'height\'.\n            else {\n                *it = height;\n            }\n        }\n\n        // The size of \'ans\' represents the length of the longest increasing subsequence.\n        return ans.size();\n    }\n};\n```\n\n# Java Code\n```\nclass Solution {\n    public int maxEnvelopes(int[][] envelopes) {\n        // Sort envelopes by width in ascending order. \n        // If two envelopes have the same width, sort by height in descending order.\n        Arrays.sort(envelopes, (a, b) -> {\n            if (a[0] == b[0]) return b[1] - a[1];\n            return a[0] - b[0];\n        });\n\n        // Extract the heights into a separate list.\n        int[] heights = new int[envelopes.length];\n        for (int i = 0; i < envelopes.length; i++) {\n            heights[i] = envelopes[i][1];\n        }\n\n        // The \'ans\' list will store the increasing subsequence of heights.\n        List<Integer> ans = new ArrayList<>();\n\n        for (int height : heights) {\n            // Find the position where \'height\' can be placed in \'ans\' using binary search.\n            int pos = binarySearch(ans, height);\n\n            // If \'height\' is greater than all elements in \'ans\', append it.\n            if (pos == ans.size()) {\n                ans.add(height);\n            } \n            // Otherwise, replace the element at the found position with \'height\'.\n            else {\n                ans.set(pos, height);\n            }\n        }\n\n        // The size of \'ans\' represents the length of the longest increasing subsequence.\n        return ans.size();\n    }\n\n    private int binarySearch(List<Integer> list, int target) {\n        int left = 0, right = list.size();\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (list.get(mid) < target) {\n                left = mid + 1;\n            } else {\n                right = mid;\n            }\n        }\n        return left;\n    }\n}\n```\n# C Code\n```\nint compare(const void *a, const void *b) {\n    int *envelopeA = *(int **)a;\n    int *envelopeB = *(int **)b;\n    if (envelopeA[0] == envelopeB[0]) {\n        return envelopeB[1] - envelopeA[1];\n    }\n    return envelopeA[0] - envelopeB[0];\n}\n\nint lower_bound(int* array, int size, int value) {\n    int left = 0, right = size;\n    while (left < right) {\n        int mid = (left + right) / 2;\n        if (array[mid] < value) {\n            left = mid + 1;\n        } else {\n            right = mid;\n        }\n    }\n    return left;\n}\n\nint maxEnvelopes(int** envelopes, int envelopesSize, int* envelopesColSize) {\n    // Sort envelopes by width in ascending order. \n    // If two envelopes have the same width, sort by height in descending order.\n    qsort(envelopes, envelopesSize, sizeof(int*), compare);\n\n    // Extract the heights into a separate list.\n    int heights[envelopesSize];\n    for (int i = 0; i < envelopesSize; i++) {\n        heights[i] = envelopes[i][1];\n    }\n\n    // The \'ans\' array will store the increasing subsequence of heights.\n    int ans[envelopesSize];\n    int ansSize = 0;\n\n    for (int i = 0; i < envelopesSize; i++) {\n        int height = heights[i];\n        // Find the position where \'height\' can be placed in \'ans\' using binary search.\n        int pos = lower_bound(ans, ansSize, height);\n\n        // If \'height\' is greater than all elements in \'ans\', append it.\n        if (pos == ansSize) {\n            ans[ansSize++] = height;\n        } \n        // Otherwise, replace the element at the found position with \'height\'.\n        else {\n            ans[pos] = height;\n        }\n    }\n\n    // The size of \'ans\' represents the length of the longest increasing subsequence.\n    return ansSize;\n}\n```\n# Python Code\n```\nclass Solution(object):\n    def maxEnvelopes(self, envelopes):\n        # Sort envelopes by width in ascending order.\n        # If two envelopes have the same width, sort by height in descending order.\n        envelopes.sort(key=lambda x: (x[0], -x[1]))\n\n        # Extract the heights into a separate list.\n        heights = [envelope[1] for envelope in envelopes]\n\n        # The \'ans\' list will store the increasing subsequence of heights.\n        ans = []\n\n        for height in heights:\n            # Find the position where \'height\' can be placed in \'ans\' using binary search.\n            pos = bisect_left(ans, height)\n\n            # If \'height\' is greater than all elements in \'ans\', append it.\n            if pos == len(ans):\n                ans.append(height)\n            # Otherwise, replace the element at the found position with \'height\'.\n            else:\n                ans[pos] = height\n\n        # The size of \'ans\' represents the length of the longest increasing subsequence.\n        return len(ans)\n```
['Binary Search', 'Dynamic Programming', 'C', 'Python', 'C++', 'Java']