Share My 39ms C++ solution with binary search


  • 0
    M

    This problem can be reduced to find longest increasing subsequence with binary search.

    Algorithm

    1. Sort the envelopes according to the first number of each envelope. If the first numbers are the same for i-th and j-th envelops , ordered them by their second number with decreasing order.
      Ex: [[2, 3], [2, 4]] --> [[2, 4], [2, 3]]

    2. After sorting, the problem become find the longest subsequence from the second number of each envelope. So, we can apply LeetCode 300's solution as following:

    Time Complexity

    1. Best case: the second number of the sorted envelopes is in increasing order. O(n)
    2. Average case: For each envelope, we have to find it position with binary search in LIS (O(log(n))). So, totally, O(nlog(n))

    Solution for finding LIS

    class Solution {
        public:
            int lengthOfLIS(vector<int>& nums) {
                int N = nums.size();
                if(N == 0) return 0;
                vector<int> LIS;
                LIS.push_back(nums[0]);
    
                for(int i = 1; i < N; i++) {
                    if(nums[i] > LIS.back())
                        LIS.push_back(nums[i]);
                    else {
                        int begin = 0, end = LIS.size() - 1;
                        while(begin <= end) {
                            int mid = begin + (end - begin) / 2;
                            if(nums[i] == LIS[mid]) {
                                begin = mid;
                                break;
                            }
                            if(nums[i] > LIS[mid])
                                begin = mid + 1;
                            else
                                end = mid - 1;
                        }
                        LIS[begin] = nums[i];
                    }
                }
                return LIS.size();
       
    

    And the solution for this problem is:

    bool cmp(pair<int, int> i, pair<int, int> j) {
        if(i.first == j.first)
            return i.second > j.second;
        return i.first > j.first;
    }
    
    class Solution {
        public:
            int maxEnvelopes(vector<pair<int, int> >& envelopes) {
                int N = envelopes.size();
                vector<pair<int, int> > LIS;
                sort(envelopes.begin(), envelopes.end(), cmp);
                LIS[0] = envelopes[0];
                for(int i = 1; i < N; i++) {
                    if(envelopes[i].second > LIS.back().second)
                        LIS.push_back(envelopes[i]);
                    else {
                        int begin = 0, end = LIS.size() - 1;
                        while(begin <= end) {
                            int mid = begin + (end - begin) / 2;
                            if(envelopes[i].second == LIS[mid].second) {
                                begin = mid;
                                break;
                            }
                            if(envelopes[i].second > LIS[mid].second)
                                begin = mid + 1;
                            else
                                end = mid - 1;
                        }
                        LIS[begin] = envelopes[i];
                    }
                }
                return LIS.size();
            }
    };
    

Log in to reply
 

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