You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.
Example 1:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Example 2:
Input: envelopes = [[1,1],[1,1],[1,1]] Output: 1
Constraints:
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105In this approach, we first sort the envelopes by width and then by height in descending order (if widths are equal). This allows us to look for the longest increasing subsequence of the heights while ignoring the widths. We then use a dynamic programming array to keep track of the maximum sequence length found so far.
This Python solution sorts the envelopes, then iterates through them to find the longest increasing subsequence of heights using binary search from the bisect module.
Java
Time Complexity: O(n log n), where n is the number of envelopes, due to sorting and binary search operations.
Space Complexity: O(n) for the dp array.
This approach involves sorting and using a binary search to optimize the search through the height for the longest increasing subsequence. This enhances efficiency over a simple dynamic programming solution due to reduced overhead from repeated searches.
This C++ solution involves sorting the envelopes and then using lower_bound to perform a binary search on the dp array, which stores the longest increasing subsequence of heights.
JavaScript
Time Complexity: O(n log n) because of sorting and binary search operations.
Space Complexity: O(n) to store the dp list.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n log n), where n is the number of envelopes, due to sorting and binary search operations. Space Complexity: O(n) for the dp array. |
| Binary Search Optimization | Time Complexity: O(n log n) because of sorting and binary search operations. Space Complexity: O(n) to store the dp list. |
Russian Doll Envelopes | Dynamic Programming | Leetcode #354 | LIS • Techdose • 29,846 views views
Watch 9 more video solutions →Practice Russian Doll Envelopes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor