O(Nlog(N)) python solution explained


  • 0
    E

    Sort the envelopes first by increasing width. For each block of same-width envelopes, sort by decreasing height.

    Then find the longest increasing subsequence of heights.

    Since each same-width subarray is non-increasing in height, we can never pick more than one height within each width (otherwise heights would be non-increasing)

    Thus, the resulting longest increasing heights subsequence is also increasing in width.

    Example:

    input

    [[5,4],[6,4],[6,7],[2,3]]
    

    sort by increasing widths, then decreasing heights:

    [[2,3],[5,4],[6,7],[6,4]]
    

    Get the heights:

    [3,4,7,4]
    

    Find the length longest increasing subsequence:

    [3,4,7]
    

    (Note that we could not have picked more than one evelope with width 6)

    Answer: 3

    class Solution(object):
        def maxEnvelopes(self, envs):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            # sort first by increasing width
            # within each subarray of same-width envelopes
            # sort by decreasing height
            envs.sort(key=lambda (w,h): (w,-h))
            
            # now find the length of the longest increasing subsequence of heights.
            # Since each same-width block was sorted non-increasing, 
            # we can only pick at most one height within each block
            # otherwise, the sequence would be non-increasing
            tails=[]
            for (w,h) in envs:
                idx=bisect.bisect_left(tails, h)
                if idx==len(tails):
                    tails.append(h)                        
                elif idx==0 or tails[idx-1]<h:
                    tails[idx]=h
            return len(tails)    
    

Log in to reply
 

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