O(n logn) Python solution with binary search

  • 1

    Idea: keep an array best that stores for each index i the lowest ending value of a subsequence with length i+1.

    • best[0] = lowest value found so far
    • best[1] = lowest ending value of a subsequence with length 2 found so far
    • best[2] = lowest ending value of a subsequence with length 3 found so far

    And so on

    In the end, the elements of best will contain one of the longest subsequences. It's length is the answer of the problem.

    To have an O(n logn) time complexity, for each of the n elements in the input array nums, we binary-search the element of best to be updated.

    best has at most n elements, eventually much less (worst case being an increasingly sorted input array), hence the logn.

    For the example input [10,9,2,5,3,7,101,18], best will be in the end [2, 3, 7, 18], with length 4.

    class Solution(object):
        def lengthOfLIS(self, nums):
            if not nums:  return 0
            best = [nums[0]]
            for i in range(1, len(nums)):
                index = self.upperBound(best, nums[i], 0, len(best))
                if index == len(best): best.append(nums[i])
                else: best[index] = nums[i]
            return len(best)
        # Return smallest index i such that array[i] >= target
        # or return end+1 if none (target > all array elements)
        def upperBound(self, array, target, start, end):
            if start >= end: return start
            m = (end+start)//2
            if array[m] >= target:
                if m == start or array[m-1] < target: return m
                return self.upperBound(array, target, start, m)
            return self.upperBound(array, target, m+1, end)

Log in to reply

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