5-line O(nlog(n)) Python with readability and explanations


  • 1

    In this DP/binary-search algorithm, tail[i] stores the smallest last element of all increasing subsequences with length i+1. tail is originally []. We update tail as we get more and more numbers from nums.

    Important: tail is always strictly increasing! (Note that in the statement of this problem, 'increasing' actually means 'strictly increasing')

    Whenever we have a new number x from nums, we can binary-search tail to find out the longest subsequence to prolong. We will update and only update this element of tail.

            tail = []
            for x in nums:
                pos = bisect.bisect_left(tail, x) # find the position "pos" so that tail[i] < x for all i < pos
                tail[pos:pos+1] = [x]             # if tail[pos] exists, update it to be x, otherwise append x
            return len(tail)
    

    This brilliant idea belongs to @dietpepsi , I just rewrite it. His original post is here.


Log in to reply
 

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