Russian Doll Envelopes — 2D LIS

Problem

Envelopes can be nested if both dimensions are strictly smaller. Find max nesting count.

Approach — Sort + LIS

Sort by (w, -h). Then LIS on heights. The -h trick ensures same-width envelopes can't both be in the subsequence.

Time: O(n log n) | Space: O(n)

Solutions

Python

import bisect
class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        envelopes.sort(key=lambda x:(x[0],-x[1]))
        tails=[]
        for _,h in envelopes:
            pos=bisect.bisect_left(tails,h)
            if pos==len(tails): tails.append(h)
            else: tails[pos]=h
        return len(tails)

C++

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& env){
        sort(env.begin(),env.end(),[](auto& a,auto& b){return a[0]<b[0]||(a[0]==b[0]&&a[1]>b[1]);});
        vector<int> tails;
        for(auto& e:env){
            auto it=lower_bound(tails.begin(),tails.end(),e[1]);
            if(it==tails.end()) tails.push_back(e[1]);
            else *it=e[1];
        }
        return tails.size();
    }
};

Complexity

Time: O(n log n) | Space: O(n)