Russian Doll Envelopes

Practice Link

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 (put one inside the other).

Intuition#

This is a 2D version of Longest Increasing Subsequence — an envelope can hold another only if it's strictly bigger in both dimensions, and we want the longest chain of such nestings.

The standard trick: sort by width ascending, and reduce the problem to a 1D LIS on height. Once widths are sorted, any valid nesting chain automatically has non-decreasing width as you scan left to right, so all that's left to guarantee is strictly increasing height — a plain LIS on the height column.

The subtlety is same-width envelopes. Two envelopes with equal width can never nest inside each other no matter their heights, but a naive height-LIS wouldn't know that — it would happily chain (3,4) → (3,5) → (3,6) since heights are increasing. The fix is the tie-break: for equal widths, sort by height descending. That way, when several same-width envelopes appear together, the LIS on heights processes them in decreasing order, which means each one can only ever shrink an existing subsequence's tail, never extend one — so they can never accidentally count as chaining into each other. A genuine extension only happens once a strictly larger width shows up.

Once the array is sorted this way, the problem is exactly "find the length of the LIS of the height column," which is solved with the O(n log n) patience-sorting technique instead of the O(n²) DP (needed here since n can be up to 10⁵, and O(n²) TLEs):

• Maintain lis, where lis[k] is the smallest possible tail height for an increasing subsequence of length k+1. lis is always sorted.
• For each incoming height ele, binary search (lower_bound) for the first tail >= ele.
  • If none exists (idx == lis.size()), ele is bigger than every current tail, so it extends the longest chain found so far — push it.
  • Otherwise, ele can replace that tail with a smaller value, keeping the same subsequence length but leaving more room for future extensions — overwrite lis[idx] = ele.
• lis.size() at the end is the LIS length, which (thanks to the sort) is the answer.

Brute Force: O(n²) DP#

Sort the same way (width ascending, height descending on ties), then run plain LIS DP on the height column: lis[i] = length of the longest chain ending at envelope i, extended from any earlier j with a strictly smaller height.

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](vector<int> &a, vector<int> &b){
            if(a[0] == b[0])
                return a[1] > b[1];
            
            return a[0] < b[0];
        });

        vector<int> lis(n,1);

        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(envelopes[i][1] > envelopes[j][1]){
                    lis[i] = max(lis[i], 1 + lis[j]);
                }
            }
        }

        return *max_element(lis.begin(), lis.end());
    }
};

Time Complexity: O(n²) — nested loop over all pairs (i, j). This TLEs on LeetCode since n can be up to 10⁵.

Space Complexity: O(n) for the lis array.

This is correct — the sort's tie-break already prevents same-width envelopes from chaining — but too slow. Same recurrence, faster search: instead of scanning every earlier j to find the best one to extend, binary search for it.

Solution: O(n log n) Patience Sorting#

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](vector<int> &a, vector<int> &b){
            if(a[0] == b[0])
                return a[1] > b[1];
            
            return a[0] < b[0];
        });

        vector<int> lis;

        for(int i=0;i<n;i++){
            int ele = envelopes[i][1];
            int idx = lower_bound(lis.begin(), lis.end(), ele) - lis.begin();

            if(idx >= lis.size())
                lis.push_back(ele);
            else
                lis[idx] = ele;
            // cout<<lis[i]<<endl;
        }

        return lis.size();

    }
};

Dry run#

envelopes = [[5,4],[6,4],[6,7],[2,3]]

Sort (width ascending, height descending on width ties — [6,7] before [6,4]):

[2,3], [5,4], [6,7], [6,4]

Sweep:

lis.size() = 3, matching the actual chain [2,3] → [5,4] → [6,7].

Complexities#

Let n = number of envelopes.

Time Complexity: O(n log n) — O(n log n) for the sort, plus O(n log n) for the sweep (one lower_bound binary search per envelope).

Space Complexity: O(n) for the lis array (ignoring the space used by sort itself).