Python O(NlgN) LIS Binary Search


  • 0
    H

    Reduce to LIS by sorting in ascending fashion for one of the variables, and sorting in descending fashion if there is a tie.
    Note O(N^2) LIS solution gives TLE

    class Solution(object):
        def maxEnvelopes(self, envelopes):
            if len(envelopes) == 0:
                return 0
            envelopes.sort(key=lambda x: (x[0], -x[1]))
            dp = [envelopes[0][1]]
            max_lis = 1
            for i in range(1, len(envelopes)):
                if envelopes[i][1] < dp[0]:
                    dp[0] = envelopes[i][1]
                elif envelopes[i][1] > dp[-1]:
                    dp.append(envelopes[i][1])
                else:
                    pos = self.binarySearch(dp, envelopes[i][1], 0, len(dp)-1)
                    dp[pos] = envelopes[i][1]
                max_lis = max(len(dp), max_lis)
            return max_lis
        
        def binarySearch(self, A, target, first, last):
            while first < last:
                middle = (first+last)//2
                if A[middle] >= target:
                    last=middle
                else:
                    first=middle+1
            return first
            
            
    

Log in to reply
 

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