Python Easy O(n) Solution


  • 37
    G

    Start with the maximum numbers for the first and second element. Then:
    (1) Find the first smallest number in the 3 subsequence
    (2) Find the second one greater than the first element, reset the first one if it's smaller

    def increasingTriplet(nums):
        first = second = float('inf')
        for n in nums:
            if n <= first:
                first = n
            elif n <= second:
                second = n
            else:
                return True
        return False

  • 0
    W

    @girikuncoro

    Freaking AWWWWSOME!


  • 0

    @girikuncoro Cool!


  • 0
    B

    @girikuncoro I noticed that the solution doesn't keep track of the elements in the subsequence properly: e.g. if you have the array [5,1,5,5,0,8], the function returns true, but has first = 0, second=5, third = 8. first doesn't really represent the first value in the subsequence, rather the min value in the array. But it works out because second represents a value that is greater than some other value preceding it (in this case, 1). My proposal to keep track of the actual subsequence is below (I tested it out with a few cases, and it works so far):

    def increasingTriplet(self,nums):
        first = second = secondMin = float('inf')
        for n in nums:
            if n <= first:
                if second < float('inf'):
                    secondMin = first
                first = n                
            elif n <= second:
                second = n
            else:
                secondMin = first if secondMin == float('inf') else secondMin
                print "first: {}, second: {}, third: {}".format(secondMin, second, n)
                return True
        return False

  • 0

    @borus I believe the OP's algorithm is similar to the "Longest Increasing Sub-sequence" problem. First, second, and third actually represent the lowest ending value of increasing sub-sequences of length one, two, and three respectively.


  • 0
    J

    @borus said in Python Easy O(n) Solution:

    [5,1,5,5,0,8]

    It doesn't work for [5,1,5,5,0,0,0,0,8].


Log in to reply
 

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