Python O(n) Time O(1) Space. Extendable to the Longest Subsequence problem.

  • 0

    If you replace the while loop with a binary search, get rid of the if statement, and increase the size of vals to the length of the array, you have a O(nlogn) solution for the "Longest Subsequence" problem.

        def increasingTriplet(self, nums):
            vals = [float('inf')] * 2
            for n in nums:
                i = 1
                while i >= 0 and vals[i] >= n:
                    i -= 1
                if i == 1: 
                    return True
                vals[i+1] = n
            return False

Log in to reply

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