Python O(n)


  • 0

    pre-process so that I known if there is a1 < nums[i] and a2 > nums[i], and if there are, should return True, else return False

    class Solution(object):
        def increasingTriplet(self, nums):
            if len(nums) < 3:
                return False
            less, more = [ 0 for i in xrange(len(nums)) ], [ 0 for i in xrange(len(nums)) ]
            mini = nums[0]
            for i in xrange(1, len(nums)):
                if nums[i] > mini:
                    less[i] = 1
                else:
                    mini = nums[i]
            maxim = nums[-1]
            for i in xrange(len(nums) - 2, -1, -1):
                if nums[i] < maxim:
                    more[i] = 1
                else:
                    maxim = nums[i]
            for i in xrange(len(nums)):
                if less[i] and more[i]:
                    return True
            return False
    

Log in to reply
 

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