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).
This highly efficient approach cleverly reduces the 2D nesting problem into a 1D Longest Increasing Subsequence (LIS) problem. This is achieved through a special sorting strategy. Once sorted, the problem is equivalent to finding the LIS of the heights of the envelopes, which can be solved in O(N log N) time using binary search.
Algorithm
- Sort the
envelopesarray using a custom comparator. The primary sort key is width (ascending). If widths are equal, the secondary sort key is height (descending). - Initialize an empty list,
sub, which will be used to find the Longest Increasing Subsequence (LIS) of heights. - Iterate through each
envelopein the sorted array:- Let
heightbe the current envelope's height (envelope[1]) - Perform a binary search for
heightin thesublist. - If
heightis not found, the binary search will return a negative valueidx. The insertion point can be calculated asinsertionPoint = -(idx + 1). - If the
insertionPointis equal to the current size ofsub, it meansheightis greater than all elements currently insub. Appendheightto the end ofsub. - Otherwise,
heightcan replace an existing element insubto form a new, potentially better subsequence. Replace the element atinsertionPointwithheight.
- Let
- The final size of the
sublist is the length of the LIS of heights, which is the answer to the problem.
Walkthrough
The main insight is that if we sort the envelopes by width, the problem becomes finding the longest subsequence of heights that is strictly increasing. However, a simple sort by width is not enough because it doesn't handle cases where widths are equal. For example, envelopes [6,4] and [6,7] cannot be nested, but if we just consider their heights, we might incorrectly form a chain.
To fix this, we use a custom sorting rule: sort by width in ascending order, but if widths are the same, sort by height in descending order. For [[6,4],[6,7]], this rule sorts them to [[6,7],[6,4]]. Now, when we look at their heights [..., 7, 4, ...], it's impossible for both to be part of a strictly increasing subsequence. This elegantly prevents envelopes with the same width from being in the same Russian doll chain.
After this specific sorting, the problem is reduced to finding the length of the Longest Increasing Subsequence (LIS) of the resulting sequence of heights. The standard O(N log N) algorithm for LIS can be applied. This algorithm maintains a sorted list (sub) representing the smallest possible tail for all increasing subsequences of a certain length. For each height, we use binary search to find its place in this list, either extending it or updating it to allow for longer subsequences later.
import java.util.Arrays;import java.util.ArrayList;import java.util.Collections; class Solution { public int maxEnvelopes(int[][] envelopes) { // Sort by width ascending, and for same width, by height descending. Arrays.sort(envelopes, (a, b) -> { if (a[0] == b[0]) { return b[1] - a[1]; // Descending for height } else { return a[0] - b[0]; // Ascending for width } }); // Find LIS of the heights using a patience-like sorting approach ArrayList<Integer> sub = new ArrayList<>(); for (int[] envelope : envelopes) { int height = envelope[1]; // Find the first element in sub that is >= height int idx = Collections.binarySearch(sub, height); if (idx < 0) { idx = -(idx + 1); // Calculate insertion point } if (idx == sub.size()) { // height is greater than all elements in sub, extend the LIS sub.add(height); } else { // Replace the element at idx with height // This helps to form a new LIS of the same length but with a smaller tail sub.set(idx, height); } } return sub.size(); }}Complexity
Time
O(N log N), where N is the number of envelopes. The sorting step takes `O(N log N)`. The subsequent loop runs N times, with each iteration performing a binary search which takes `O(log N)` time. Thus, the total time is dominated by these two steps.
Space
O(N), where N is the number of envelopes. This space is used for the `sub` list in the LIS algorithm, which can grow up to size N. Sorting might also use `O(N)` space depending on the implementation.
Trade-offs
Pros
Very efficient with
O(N log N)time complexity, which passes the given constraints.It's an elegant and clever reduction of a 2D problem to a well-known 1D problem (LIS).
Cons
The logic, especially the custom sorting rule and its connection to the LIS algorithm, can be less intuitive to grasp initially.
Requires familiarity with the efficient
O(N log N)algorithm for LIS.
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; }}class Solution {public: int maxEnvelopes(vector<vector<int>> &envelopes) { sort(envelopes.begin(), envelopes.end(), [](const auto &e1, const auto &e2) { return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]); }); int n = envelopes.size(); vector<int> d{envelopes[0][1]}; for (int i = 1; i < n; ++i) { int x = envelopes[i][1]; if (x > d[d.size() - 1]) d.push_back(x); else { int idx = lower_bound(d.begin(), d.end(), x) - d.begin(); if (idx == d.size()) idx = 0; d[idx] = x; } } return d.size(); }};''' >>> envelopes = [[100,100],[200,200], [1,300],[2,400],[2,401], [2,402], [3,500]] >>> envelopes.sort(key=lambda key: (key[0], -key[1])) >>> envelopes [[1, 300], [2, 402], [2, 401], [2, 400], [3, 500], [100, 100], [200, 200]] >>> >>> >>> tails = [] >>> bisect.bisect_right(tails, envelopes[0][1]) 0 >>> tails.append(envelopes[0][1]) >>> >>> bisect.bisect_right(tails, envelopes[1][1]) 1 >>> tails.append(envelopes[1][1]) >>> tails [300, 402] >>> >>> bisect.bisect_right(tails, envelopes[2][1]) # [2, 401] 1 ''' # why -key[1], not key[1]? # eg input [[4,5],[4,6],[6,7],[2,3],[1,1]] ''' >>> a = [[4,5],[4,6],[6,7],[2,3],[1,1]] >>> a.sort(key=lambda key: (key[0], -key[1])) >>> a [[1, 1], [2, 3], [4, 6], [4, 5], [6, 7]] >>> [each[1] for each in a] [1, 3, 6, 5, 7] ==> reversed 6,5 to ensure either 6 or 5 picked for longest trail, not both 6 and 5 ########## >>> a = [[4,5],[4,6],[6,7],[2,3],[1,1]] >>> a.sort(key=lambda key: (key[0])) >>> a [[1, 1], [2, 3], [4, 5], [4, 6], [6, 7]] >>> [each[1] for each in a] [1, 3, 5, 6, 7] ==> default sort to 5,6, then both 5 and 6 picked for longest trail ''' # w increasing-ordered, if w ties then h decreasing ordered. # then it's the question of Longest Increasing Subsequence for all h # (As in LC-300 Longest Increasing Subsequence) import bisect class Solution ( object ): def maxEnvelopes ( self , envelopes ): """ :type envelopes: List[List[int]] :rtype: int """ envelopes . sort ( key = lambda key : ( key [ 0 ], - key [ 1 ])) tails = [] for i in range ( 0 , len ( envelopes )): idx = bisect . bisect_left ( tails , envelopes [ i ][ 1 ]) if idx == len ( tails ): tails . append ( envelopes [ i ][ 1 ]) else : tails [ idx ] = envelopes [ i ][ 1 ] return len ( tails ) # follow up - allow rotation class Solution ( object ): def maxEnvelopes ( self , envelopes ): # Generate all possible orientations with rotation allowed all_orientations = [] for w , h in envelopes : all_orientations . append (( w , h )) # Add the rotated envelope if it results in a different orientation if w != h : all_orientations . append (( h , w )) # Sort by width and then height all_orientations . sort ( key = lambda x : ( x [ 0 ], - x [ 1 ])) # Apply LIS on the heights of the sorted envelopes def lis_heights ( seq ): tails = [] for height in seq : # Binary search idx = binary_search ( tails , height ) if idx == len ( tails ): tails . append ( height ) else : tails [ idx ] = height return len ( tails ) # similar to bisect.bisect_left() def binary_search ( tails , x ): lo , hi = 0 , len ( tails ) while lo < hi : mid = ( lo + hi ) // 2 if tails [ mid ] < x : lo = mid + 1 else : hi = mid return lo # Extract heights and apply LIS heights = [ h for _ , h in all_orientations ] return lis_heights ( heights ) # Example usage envelopes = [( 5 , 4 ), ( 6 , 4 ), ( 6 , 7 ), ( 2 , 3 )] print ( maxEnvelopes ( envelopes )) ################# class Solution ( object ): def maxEnvelopes ( self , envelopes ): """ :type envelopes: List[List[int]] :rtype: int """ envelopes . sort ( key = lambda key : ( key [ 0 ], - key [ 1 ])) tails = [] for i in range ( 0 , len ( envelopes )): ''' @note: below line different from above if use `bisect_right()`, then need to add extra if check for duplication ''' idx = bisect . bisect_right ( tails , envelopes [ i ][ 1 ]) if idx - 1 >= 0 and tails [ idx - 1 ] == envelopes [ i ][ 1 ]: continue # avoid de-dup if idx == len ( tails ): tails . append ( envelopes [ i ][ 1 ]) else : tails [ idx ] = envelopes [ i ][ 1 ] return len ( tails ) # O(N^2), overlimit if large input class Solution : def maxEnvelopes ( self , envelopes : List [ List [ int ]]) -> int : if not envelopes : return 0 n = len ( envelopes ) dp = [ 1 ] * n max_len = 1 envelopes . sort ( key = lambda x : ( x [ 0 ], - x [ 1 ])) for i in range ( 1 , n ): for j in range ( i ): if envelopes [ j ][ 0 ] < envelopes [ i ][ 0 ] and envelopes [ j ][ 1 ] < envelopes [ i ][ 1 ]: dp [ i ] = max ( dp [ i ], dp [ j ] + 1 ) max_len = max ( max_len , dp [ i ]) return max_len ############ class Solution : def maxEnvelopes ( self , envelopes : List [ List [ int ]]) -> int : envelopes . sort ( key = lambda x : ( x [ 0 ], - x [ 1 ])) d = [ envelopes [ 0 ][ 1 ]] for _ , h in envelopes [ 1 :]: if h > d [ - 1 ]: d . append ( h ) else : idx = bisect_left ( d , h ) if idx == len ( d ): idx = 0 d [ idx ] = h return len ( d )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.