Python solution based on LIS


  • 3
    G

    It's a problem based on LIS.
    DP solution for LIS is N^2 which will TLE here.
    Using Binary Search approach will get accepted.

    https://leetcode.com/problems/longest-increasing-subsequence/

    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        if not envelopes:
            return 0
        
        l = len(envelopes)
        if l == 1:
            return 1
        
        envelopes.sort(
            cmp = lambda x, y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1]) 
        # sort the envelopes by width because they need to be inorder before consider the heigths or versa
        
        width = []
        for i in envelopes:
            width.append(i[1])
            
        res = self.longestSubsequence(width)
        # the problem became LIS after sort(width)
        
        return res
        
        
    
    def longestSubsequence(self, nums):
        """
        return type: int (number of longest subsequence)
        """
        if not nums:
            return 0
        l = len(nums)
        res = []
        
        for num in nums:
            pos = self.binarySearch(num, res)
            if pos >= len(res):
                res.append(num)
            else:
                res[pos] = num
        
        return len(res)
        
        
    
    def binarySearch(self, target, nums):
        """
        return type: int (ceiling of the insert position)
        """
        if not nums:
            return 0
        
        l = len(nums)
        start = 0
        end = l - 1
        
        while start <= end:
            half = start + (end - start) // 2
            if nums[half] == target:
                return half
            elif nums[half] < target:
                start = half + 1
            else:
                end = half - 1
            
        return start
    

    '''


  • 0
    P

    Wow, nice, I learned a beautiful solution from your post.
    We can use bisect module to make the code concise.

    class Solution(object):
        def maxEnvelopes(self, envelopes):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            if not envelopes:
                return 0
            envelopes.sort(key=lambda c:(c[0],-c[1]))
            return self.longestSubsequece(list(map(lambda c: c[1], envelopes)))
    
        def longestSubsequece(self, arr):
            q = []
            for i in arr:
                pos = bisect.bisect_left(q, i)
                if len(q) == pos:
                    q.append(i)
                else:
                    q[pos] = i
            return len(q)
    

    Almostly same as yours.


Log in to reply
 

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