Welcome to Subscribe On Youtube
354. Russian Doll Envelopes
Description
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 <= 105
Solutions
Consider a situation [100,100],[200,200], [1,300],[2,400],[3,500].
If you only update x in p(x,y) every time, then the next three will be thrown away, and the maximum value is 2, while correct reulst should be 3.
First, we must sort all the envelopes from smallest to largest.
- First row according to the width from small to large,
- If the width is the same, then the height is smaller and then the front,
Then we start to traverse, for each envelope, we traverse all the envelopes before it,
- If the length and width of the current envelope are larger than those of the previous envelope, then we update the dp array by
dp[i] = max(dp[i], dp[j] + 1). - Then every time we traverse an envelope, we update the result
Follow up - If the envelope can be rotated. What is the longest sequence?
With rotation allowed, an envelope that is initially wider than taller can be rotated 90 degrees to make it taller than wide, potentially allowing it to fit into another envelope it couldn’t before, or vice versa.
To approach this modified problem, you would need to consider both orientations of each envelope when determining if one can fit into another. Here’s a strategy on how you might tackle the problem with rotation allowed:
1. Generate All Orientations:
For each envelope, consider both possible orientations: (width, height) and (height, width), but only if rotating it gives a different dimension. This effectively doubles the number of envelopes you have to consider, except for squares which remain unchanged upon rotation.
To enqueue <3,4>, then <4,3> also enqueue, and then find the longest sequence.
2. Sort and Remove Duplicates:
Sort all generated envelopes first by width and then by height. However, because an envelope in one orientation might be identical to another envelope or even the same envelope in a different orientation, you’ll need to remove duplicates to ensure each unique envelope is considered only once.
3. Dynamic Programming (DP) or Patience Sorting:
After sorting and deduplicating, you can apply a similar approach to the one used in the original problem. However, the decision to include an envelope in your sequence now must consider the possibility that its alternate orientation could lead to a different sequence of envelopes.
-
Dynamic Programming: Iterate through the sorted list, and for each envelope, check all previously considered envelopes to see if it fits. Keep track of the longest sequence formed with each envelope as the last one in the sequence. This approach has a time complexity of O(N^2) for N envelopes (considering both orientations).
-
Patience Sorting (Binary Search): A more efficient approach involves modifying the
longest increasing subsequence algorithm (LIS)using binary search (patience sorting technique). For each envelope, find the place where it fits in the “stack” of increasing envelopes, considering both dimensions. This approach has a time complexity of O(N log N).
Challenges with Rotation:
- Overlap: Allowing rotation introduces more complexity in comparing envelopes since an envelope could potentially fit into another in more than one way.
- Optimization: The rotation adds more possibilities to consider, making the optimization more challenging. You’ll need to carefully handle cases where rotating an envelope might allow it to fit into others that it couldn’t before, or alternatively, prevent it from fitting into an envelope it could before rotation.
Below Python Code Explanation:
-
All Orientations: For each envelope, both orientations
(w, h)and(h, w)are considered, unless they are the same (which happens whenw == h, i.e., the envelope is square). -
Sorting: The envelopes are sorted by width in ascending order and by height in descending order within the same width. Sorting by height in descending order ensures that when we apply the LIS algorithm on heights, we correctly handle envelopes with the same width but different heights.
-
LIS on Heights: After sorting, the problem reduces to finding the Longest Increasing Subsequence of the heights. This part is solved using a variation of the classic LIS algorithm, where we maintain an array
tailsto keep track of the smallest possible tail for all increasing subsequences of lengthi + 1intails[i]. -
Binary Search: For each height, we use binary search to find the position in the
tailsarray where it can be placed or replaced. This step ensures the algorithm runs inO(N log N)time complexity, whereNis the total number of orientations considered.
-
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) -
func maxEnvelopes(envelopes [][]int) int { sort.Slice(envelopes, func(i, j int) bool { if envelopes[i][0] != envelopes[j][0] { return envelopes[i][0] < envelopes[j][0] } return envelopes[j][1] < envelopes[i][1] }) n := len(envelopes) d := make([]int, n+1) d[1] = envelopes[0][1] size := 1 for _, e := range envelopes[1:] { x := e[1] if x > d[size] { size++ d[size] = x } else { left, right := 1, size for left < right { mid := (left + right) >> 1 if d[mid] >= x { right = mid } else { left = mid + 1 } } if d[left] < x { left = 1 } d[left] = x } } return size }