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 <= 105Problem Overview: You are given envelopes with width and height. One envelope can fit inside another only if both width and height are strictly larger. The task is to compute the maximum number of envelopes you can nest inside each other, similar to Russian dolls.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
Start by sorting envelopes by width in ascending order. If widths are equal, sort by height to keep ordering consistent. After sorting, the problem becomes similar to finding the longest increasing subsequence (LIS) based on envelope height while ensuring widths increase. Use a DP array where dp[i] stores the maximum number of envelopes ending with envelope i. Iterate through previous envelopes and update dp[i] when both width and height are increasing. This approach clearly demonstrates the relationship to dynamic programming, but the nested loop results in O(n²) time.
Approach 2: Binary Search Optimization (O(n log n) time, O(n) space)
The optimal solution converts the problem into a longest increasing subsequence on heights. First sort envelopes by width ascending, but when widths are equal sort heights in descending order. This trick prevents envelopes with the same width from being counted in the subsequence. After sorting, extract heights and compute LIS using a binary search technique. Maintain a list where each element represents the smallest possible tail for an increasing subsequence of a given length. For every height, use binary search to find the replacement position. This reduces the LIS computation to O(n log n). The method combines sorting, array traversal, and binary search to achieve optimal performance.
Recommended for interviews: The binary search LIS approach is the expected solution in most interviews because it improves the complexity from O(n²) to O(n log n). Still, explaining the DP formulation first shows that you understand the subsequence relationship before optimizing it with binary search.
In 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.
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.
C++
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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (LIS style) | O(n²) | O(n) | Good for understanding the LIS relationship and when constraints are small. |
| Binary Search LIS Optimization | O(n log n) | O(n) | Preferred for large inputs and the standard optimal interview solution. |
Russian Doll Envelopes | Dynamic Programming | Leetcode #354 | LIS • Techdose • 35,417 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