Watch 10 video solutions for Russian Doll Envelopes, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by Techdose has 35,417 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |