Clean and short nlogn solution


  • 8
    J

    See more explanation in Longest Increasing Subsequence Size (N log N)

    def maxEnvelopes(self, envelopes):
        def bin_search(A, key):
            l, r = 0, len(A)
            while l < r:
                mid = (l+r)/2
                if A[mid][1] < key[1]:
                    l = mid + 1
                else:
                    r = mid
            return l
        envelopes.sort(
            cmp = lambda x,y: x[0]-y[0] if x[0] != y[0] else y[1]-x[1])
        n = len(envelopes)
        tails = []
        for i in range(n):
            e = envelopes[i]
            p = bin_search(tails, e)
            if p == len(tails):
                tails.append(e)
            else:
                tails[p] = e
        return len(tails)
    

  • 0
    Y

    Clear Answer. Add a C++ version:

    bool cmp(pair<int, int> &p1, pair<int, int> &p2) {
     return p1.first < p2.first || p1.first == p2.first && p1.second > p2.second;
    }
    
    int maxEnvelopes(vector<pair<int, int>> &envelopes) {
      if (envelopes.size() < 2) {
        return envelopes.size();
      }
    
      sort(envelopes.begin(), envelopes.end(), cmp);
    
      vector<pair<int, int>> maxLenWithMin(envelopes.size() + 1);
      int maxLen = 1;
      maxLenWithMin[1] = envelopes[0];
      for (int i = 1; i < envelopes.size(); i++) {
        int index = binarySearch(maxLenWithMin, maxLen, envelopes[i]);
        if (index > maxLen) {
          maxLen++;
        }
        maxLenWithMin[index] = envelopes[i];
      }
    
      return maxLen;
    }
    
    // a[i-1] < b =< a[i], return i
    int binarySearch(vector<pair<int, int>> &maxLenWithMin, int maxLen,
                   pair<int, int> &target) {
      int l = 1;
      int r = maxLen;
    
      if (target.second > maxLenWithMin[r].second) {
        return r + 1;
      }
    
      if (target.second <= maxLenWithMin[l].second) {
        return l;
      }
    
      while (l + 1 != r) {
        int mid = l + (r - l) / 2;
        if (target.second > maxLenWithMin[mid].second) {
          l = mid;
        } else {
          r = mid;
        }
      }
    
      return r;
    }
    

  • 5
    C

    Nice solution! I had a similar solution, but never get it right, as I sorted envelopes by using the default comparing function,
    the y[1]-x[1] part in cmp = lambda x,y: x[0]-y[0] if x[0] != y[0] else y[1]-x[1] is actually very important!

    Here is my solution with your cmp function, works finally :)

    def maxEnvelopes(envelopes):
        envelopes.sort(
            cmp = lambda x,y: cmp(x[0], y[0]) if x[0] != y[0] else cmp(y[1], x[1]))
        lst = [x[1] for x in envelopes]
        tails = []
        for e in lst:
            p = bisect.bisect_left(tails, e)
            if p == len(tails):
                tails.append(e)
            else:
                tails[p] = e
        return len(tails)

  • 1
    F

    So, here is an even shorter version, using lambda for sorting and bisect.bisect_left for binary search.

    import bisect
    class Solution(object):
        def maxEnvelopes(self, envelopes):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            envelopes.sort(key = lambda x: (x[0], -x[1]))
            
            dp = []
            for x in envelopes:
                i = bisect.bisect_left(dp, x[1])
                if i == len(dp):
                    dp.append(x[1])
                else:
                    dp[i] = x[1]
            
            return len(dp)
    

  • 0
    Z
    class Solution(object):
        def maxEnvelopes(self, envelopes):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            envelopes.sort(key=lambda x: (x[0], -x[1]))
            dp = [sys.maxsize] * len(envelopes)
            for e in envelopes:
                dp[bisect.bisect_left(dp, e[1])] = e[1]
            return bisect.bisect_left(dp, sys.maxsize)
    

Log in to reply
 

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