Simple and short, easy to understand LIS based solution C++. time= O(NlogN), Space= O(N)

  • 0
    1. Sort the list by either w (or h) as key.(take care of equal case)
    2. Apply LIS on sorted list with h(or w) as key.(take care of equal case)
    static bool comp(pair<int, int> a, pair<int, int> b) //sort on the basis of w as key
        if(a.first == b.first)
            return a.second<b.second; // sort entries with h as key when w is same
        return a.first<b.first;
    class Solution {
        int maxEnvelopes(vector<pair<int, int>>& envelopes) {
            sort(envelopes.begin(), envelopes.end(), comp); // sort the vector
            int maxx =0;
            for(int i =1; i<envelopes.size() ;i++)
                for(int j =0; j<i; j++)
                    if(envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second && LIS[i]<LIS[j]+1) // takes care of == case of w in sorted list
                        LIS[i] = LIS[j]+1;
                        maxx = max(maxx,LIS[i]);
            return maxx;

  • 6

    this is N^2 , not NlogN

Log in to reply

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