Russian Doll Envelopes
HardPrompt
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:
3Example 2:
Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
Constraints:
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach frames the problem as a classic Longest Increasing Subsequence (LIS) problem in two dimensions. It begins by sorting the envelopes, primarily by their width. Then, it uses dynamic programming to build the solution. A dp array is used where dp[i] represents the length of the longest possible chain of Russian doll envelopes ending with the i-th envelope.
Algorithm
- Sort the
envelopesarray. The primary sorting key is width (ascending), and the secondary key is height (also ascending). - Create a
dparray of sizen(the number of envelopes), and initialize all its elements to1.dp[i]will store the length of the longest Russian doll chain ending withenvelopes[i]. - Initialize a variable
maxLento1(or0if the input can be empty) to keep track of the maximum length found so far. - Iterate through the envelopes from
i = 1ton-1.- For each
i, iterate through all previous envelopes fromj = 0toi-1. - If
envelopes[j]can fit insideenvelopes[i](i.e.,envelopes[j][0] < envelopes[i][0]andenvelopes[j][1] < envelopes[i][1]), it means we can extend the chain ending atj. - Update
dp[i]using the formula:dp[i] = max(dp[i], 1 + dp[j]).
- For each
- After the inner loop for
ifinishes, updatemaxLen = max(maxLen, dp[i]). - After the outer loop finishes,
maxLenholds the result.
Walkthrough
The fundamental idea is to determine, for each envelope, the longest chain that can end with it. To do this systematically, we first sort the envelopes. Sorting by width (and then height, for consistency) ensures that if envelope j can contain envelope i, j will likely appear after i in the sorted array, simplifying our search for predecessors.
We define dp[i] as the length of the longest chain of envelopes that can be formed, with envelopes[i] being the outermost envelope. Initially, every envelope can form a chain of length 1 by itself, so we initialize all dp values to 1.
We then iterate through each envelope i from the beginning. For each i, we look back at all preceding envelopes j (j < i). If envelopes[j] can fit inside envelopes[i] (both width and height are smaller), we can potentially extend the chain that ended at j. The new chain length would be 1 + dp[j]. We take the maximum over all such valid j's to find the optimal length for dp[i]. The overall maximum value encountered in the dp array gives the final answer.
import java.util.Arrays;import java.util.Comparator; class Solution { public int maxEnvelopes(int[][] envelopes) { if (envelopes == null || envelopes.length == 0) { return 0; } // Sort envelopes by width ascending, then by height ascending Arrays.sort(envelopes, new Comparator<int[]>() { public int compare(int[] a, int[] b) { if (a[0] == b[0]) { return a[1] - b[1]; } else { return a[0] - b[0]; } } }); int n = envelopes.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // Check if envelope j can be put inside envelope i if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) { dp[i] = Math.max(dp[i], 1 + dp[j]); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; }}Complexity
Time
O(N^2), where N is the number of envelopes. The sorting step takes `O(N log N)`, but it is dominated by the nested loops for the dynamic programming calculation, which take `O(N^2)` time.
Space
O(N), where N is the number of envelopes. This is for the `dp` array used to store the lengths of the subsequences.
Trade-offs
Pros
It's a direct and intuitive application of dynamic programming for LIS-type problems.
The logic is relatively easy to follow and implement.
Cons
The
O(N^2)time complexity is inefficient and will likely lead to a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints (Nup to 10^5).
Solutions
Solution
class Solution {public int maxEnvelopes(int[][] envelopes) { Arrays.sort( envelopes, (a, b)->{ return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]; }); int n = envelopes.length; int[] d = new int[n + 1]; d[1] = envelopes[0][1]; int size = 1; for (int i = 1; i < n; ++i) { int x = envelopes[i][1]; if (x > d[size]) { d[++size] = x; } else { int left = 1, right = size; while (left < right) { int mid = (left + right) >> 1; if (d[mid] >= x) { right = mid; } else { left = mid + 1; } } int p = d[left] >= x ? left : 1; d[p] = x; } } return size; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.