Sort pairs by first element then find LIS in second element O(nlogn)

  • 0

    The only tricky part is to make sure envelopes with same width should not be counted towards the LIS sequence, for that, we use a custom sort function that returns true iff

    A.first < B.first || (A.first == B.first && A.second > B.second)

    class Solution {
        int maxEnvelopes(vector<pair<int, int>>& envelopes) {
            if (envelopes.empty())
                return 0;
            sort(envelopes.begin(), envelopes.end(), cmpPair);
            vector<int> table;
            // below is binary search for LIS
            for (int i = 1; i < envelopes.size(); i++){
                if (envelopes[i].second > table[table.size() - 1])
                    table[lower_bound(table.begin(), table.end(), envelopes[i].second) - table.begin()]= envelopes[i].second;
            return table.size();
        static bool cmpPair(const pair <int, int> &a, const pair <int, int> &b){
            return a.first < b.first || (a.first == b.first && a.second > b.second);// a.second > b.second makes sure same width envelops won't be counted towards the LIS sequence in height :p

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.