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


  • 0
    S
    Logic:
    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 {
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes) {
            sort(envelopes.begin(), envelopes.end(), comp); // sort the vector
            vector<int>LIS(envelopes.size(),1);
            int maxx =0;
            if(envelopes.size()>0)
                maxx=1;
            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
    X

    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.