# Python Easy O(n) Solution

• 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``````

• @girikuncoro

Freaking AWWWWSOME!

• @girikuncoro Cool!

• @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``````

• @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.

• @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].

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