# Russian Doll Envelopes
**Difficulty:** HARD
[External](https://leetcode.com/problems/russian-doll-envelopes)
Canonical: https://scaleengineer.com/dsa/problems/russian-doll-envelopes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Intuit](https://scaleengineer.com/companies/intuit), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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 <= 105`
* `envelopes[i].length == 2`
* `1 <= wi, hi <= 105`

# Approaches
## Dynamic Programming
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.
**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.
**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 (`N` up to 10^5).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Sort the `envelopes` array. The primary sorting key is width (ascending), and the secondary key is height (also ascending).
- Create a `dp` array of size `n` (the number of envelopes), and initialize all its elements to `1`. `dp[i]` will store the length of the longest Russian doll chain ending with `envelopes[i]`.
- Initialize a variable `maxLen` to `1` (or `0` if the input can be empty) to keep track of the maximum length found so far.
- Iterate through the envelopes from `i = 1` to `n-1`.
  - For each `i`, iterate through all previous envelopes from `j = 0` to `i-1`.
  - If `envelopes[j]` can fit inside `envelopes[i]` (i.e., `envelopes[j][0] < envelopes[i][0]` and `envelopes[j][1] < envelopes[i][1]`), it means we can extend the chain ending at `j`.
  - Update `dp[i]` using the formula: `dp[i] = max(dp[i], 1 + dp[j])`.
- After the inner loop for `i` finishes, update `maxLen = max(maxLen, dp[i])`.
- After the outer loop finishes, `maxLen` holds the result.

## Sort and Binary Search (LIS)
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.
**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.
**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.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
- Sort the `envelopes` array 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 `envelope` in the sorted array:
  - Let `height` be the current envelope's height (`envelope[1]`)
  - Perform a binary search for `height` in the `sub` list.
  - If `height` is not found, the binary search will return a negative value `idx`. The insertion point can be calculated as `insertionPoint = -(idx + 1)`.
  - If the `insertionPoint` is equal to the current size of `sub`, it means `height` is greater than all elements currently in `sub`. Append `height` to the end of `sub`.
  - Otherwise, `height` can replace an existing element in `sub` to form a new, potentially better subsequence. Replace the element at `insertionPoint` with `height`.
- The final size of the `sub` list is the length of the LIS of heights, which is the answer to the problem.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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();
  }
};

```

### Python

```python
''' >>> 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 )
```