Another O(n log n) Python


  • 4

    minend[i] is the minimum ending of an increasing subsequence of length i+1.

    def lengthOfLIS(self, nums):
        minend = [float('inf')] * (len(nums) + 1)
        for num in nums:
            minend[bisect.bisect_left(minend, num)] = num
        return minend.index(float('inf'))

  • 1
    K

    bisect.bisect_left can avoid (len(nums) + 1) : )

    def lengthOfLIS(self, nums):
        minend = [float('inf')] * len(nums)
        for num in nums:
            minend[bisect.bisect_left(minend, num)] = num
        return bisect.bisect_left(minend, float('inf'))

  • 0

    Good alternative. I do like my sentinels, but yours is maybe more straight-forward, and sliiightly faster in each iteration and faster in the final search. And I don't think I thought of doing it your way, so thanks :)


  • 0
    K

    No problem :)


  • -1
    Y

    @StefanPochmann the problem is that if you are working with somebody, they will not be happy to maintain your code~~


  • 0
    B

    Is this space efficient for large arrays ?


Log in to reply
 

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