354. Russian Doll Envelopes - cocoder39/coco39_LC GitHub Wiki

354. Russian Doll Envelopes

2D 300. Longest Increasing Subsequence

Notes 2020:

Option 1: O(n^2) DP

Option 2: O(n * logn) binary search

Sorting envelopes by one dimension (eg, width) can convert this problem to 1-D LIS problem

1. Suppose the width is strictly increasing after sorting, then the problem is equal to finding the LIS regarding to height among those sorted envelopes.
2. However, this won't work when there is a tie in width. EG, we have [3, 3] and [3, 4] after sorting then the LIS will be 2. The trick is to sort the 2nd dimension (ie, height) in descending order. If we saw [3, 4] in LIS then we will replace [3, 4] with [3, 3], which doesn't incorrectly increase the length of LIS

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        
        lis = [] # store the h 
        for w, h in envelopes:
            index = bisect.bisect_left(lis, h)
            if index == len(lis):
                lis.append(h)
            else:
                lis[index] = h
        return len(lis)

==============================================================================================================================

• sort based on width
• longest increasing sequence based on height

tips

• if all widths are different, the problem is reduced to 300. Longest Increasing Subsequence
• if there are envelopes with equal width w. since one envelope can contain another only if it has both greater width and height. so if an envelope with width w in the sequence, there can be only one envelope with width w. The problem is selecting which one among all envelopes with width w. Hence, when inserting elements with equal height into LIS, we hope to insert wider element first, then the other one would replace the wider one, maintaining the length of LIS. On the contrary, if insert wider one later, it would increase the length of LIS, while two equal height envelopes are not allowed.

time complexity is O(n * log n)

int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), cmp); //O(n * log n)
        vector<int> LIS;
        for (auto envelope : envelopes) { //O(n * log n)
            int h = envelope.second;
            auto it = lower_bound(LIS.begin(), LIS.end(), h); //0(log n)
            if (it == LIS.end())    LIS.push_back(h);
            else                    *it = h;
        }
        return LIS.size();
    }
private:
    static bool cmp(pair<int, int>& e1, pair<int, int>& e2) {
        if (e1.first == e2.first)   return e1.second > e2.second;
        return e1.first < e2.first;
    }