Python O(nlogn) O(n) solution, beats 97%, with explanation


  • 14
    class Solution(object):
        def maxEnvelopes(self, envs):
            def liss(envs):
                def lmip(envs, tails, k):
                    b, e = 0, len(tails) - 1
                    while b <= e:
                        m = (b + e) >> 1
                        if envs[tails[m]][1] >= k[1]:
                            e = m - 1
                        else:
                            b = m + 1
                    return b
                
                tails = []
                for i, env in enumerate(envs):
                    idx = lmip(envs, tails, env)
                    if idx >= len(tails):
                        tails.append(i)
                    else:
                        tails[idx] = i
                return len(tails)
            
            
            def f(x, y):
                return -1 if (x[0] < y[0] or x[0] == y[0] and x[1] > y[1]) else 1
                
            envs.sort(cmp=f)
            return liss(envs)
    
    # Runtime: 100ms
    

    The idea is to order the envelopes and then calculate the longest increasing subsequence (LISS). We first sort the envelopes by width, and we also make sure that when the width is the same, the envelope with greater height comes first. Why? This makes sure that when we calculate the LISS, we don't have a case such as [3, 4] [3, 5] (we could increase the LISS but this would be wrong as the width is the same. It can't happen when [3, 5] comes first in the ordering).

    We could calculate the LISS using the standard DP algorithm (quadratic runtime), but we can just use the tails array method with a twist: we store the index of the tail, and we do leftmost insertion point as usual to find the right index in nlogn time. Why not rightmost? Think about the case [1, 1], [1, 1], [1, 1].


  • 0

    This is awesome. My python direct DP cannot get AC.


  • 0

    I assume it implemented the O(n^2) algorithm?


  • 0

    Yes, it is and I need more characters.


  • 1

    @agave I hope every programmer in this world could explain their thought as clear as you did.


  • 0
    T
    This post is deleted!

  • 0
    D

    @agave i guess you could also have written envelopes.sort(key=lambda x: (x[0], x[1]))
    Is the same, just using lambda and in one line :)

    BTW. just loved your right shift instead of dividing by 2 :D Really sweat


  • 0
    Y

    Shorter version using bisect

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

  • -1
    S

    @yang.zheng.904

    Hey can you please explain what you're doing or what is an algorithm captured in

            h=[]
            for i,e in enumerate(envelopes,0):
                j=bisect.bisect_left(h,e[1])
                if j<len(h):
                    h[j]=e[1]  <---- what does it do??
                else:
                    h.append(e[1])
    

  • 0
    Y

    @pshaikh
    e[1] is the height of the current envelop. h stores the heights of the envelopes before current envelop. And because envelopes are sorted by (width, -height), so current envelop's width is equal or larger than the envelopes before it. h[j] = e[1] is trying to put current envelop in the right place.


Log in to reply
 

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