Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.


Formally the function should:
Return true if there exists i, j, k  
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 
else return false.



Your algorithm should run in O(n) time complexity and O(1) space complexity.


Examples:
Given [1, 2, 3, 4, 5],
return true.


Given [5, 4, 3, 2, 1],
return false.


Credits:Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Difficulty: interview

Starter code:

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         n1 = n2 = float('inf')
         for n in nums:
             if n <= n1:
                 n1 = n
             elif n <= n2:
                 n2 = n
             else:
                 return True
         return False

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

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         first = second = float('inf')
         for n in nums:
             if n <= first:
                 first = n
             elif n <= second:
                 second = n
             else:
                 return True
         return False

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         a, b = float("inf"), float("inf")
         
         for n in nums:
             if n > b:
                 return True
             elif a < n < b:
                 b = n
             elif n < a:
                 a = n
                 
         return False

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         n=len(nums)
         if n<3:
             return False
         forward=[nums[0]]*n
         backward=[nums[-1]]*n
         for i in range(1,n):
             forward[i]=min(forward[i-1],nums[i])
         for i in range(n-2,-1,-1):
             backward[i]=max(backward[i+1],nums[i])
         for i in range(n):
             if forward[i]<nums[i]<backward[i]:
                 return True
         return False


class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums) < 3:
             return False
         
         tails = [-2147483647, nums[0]]
         
         for n in nums[1:]:
             for i in range(len(tails) - 1, -1, -1):
                 if n > tails[i]:
                     if len(tails) <= i + 1:
                         tails.append(n)
                     elif n < tails[i+1]:
                         tails[i+1] = n
                     
                     if len(tails) == 4:
                         return True
                 print(tails)
         
         return False

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         
         a=b=None;
         
         for i in nums:
             if a is None or a>=i:
                 a=i;
             elif b is None or b>=i:
                 b=i;
             else:
                 return True;
             
             
         return False;


class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         x = y = float("inf")
         
         for n in nums:
             if n <= x:
                 x = n
             elif n <= y:
                 y = n
             else:
                 return True
         
         return False

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         # keep track of the two minimum elements and see if we have a element that is larger than two
         if len(nums) < 3:
             return False
         
         minN = nums[0]
         minSecond = None
         
         for i in range(1, len(nums)):
             if type(minSecond) == int and nums[i] > minSecond:
                 return True
             
             if minN < nums[i]:  
                 if type(minSecond) == int and minSecond > nums[i]:
                     minSecond = nums[i]
                 elif not type(minSecond) == int:
                     minSecond = nums[i]
             
             minN = min(minN, nums[i])
             
             
         return False

class Solution:
     def increasingTriplet(self, nums):
         
         if len(nums) == 0:
             n = 1
         else:
             n = len(nums)
             
         index_of_A = 0
         index_of_B = n-1
         A_indices = [None] * n
         B_indices = [None] * n
     
         for i in range(2, n):
             if nums[i-1] <= nums[index_of_A]:
                 index_of_A = i-1
                 A_indices[i-1] = None
             else:
                 A_indices[i-1] = index_of_A
             if nums[n-i] >= nums[index_of_B]:
                 index_of_B = n-i
                 B_indices[n-i] = None
             else:
                 B_indices[n-i] = index_of_B
      
         for i in range(0, n):
             if A_indices[i] != None and B_indices[i] != None:
                 return True
             
         return False
             


class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if not nums:return False
         maxv=float('inf')
         minv=nums[0]
         for num in nums:
             if num>maxv:return True
             if num>minv:maxv=min(num,maxv)
             minv=min(num,minv)
         return False


class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         tails = [-float('inf')]
         for x in nums:
             for i in range(len(tails)-1, -1, -1):
                 if x > tails[i]:
                     if i == len(tails)-1:
                         tails.append(x)
                     else:
                         tails[i+1] = x
                     break
             if len(tails) == 4:
                 return True
         return False

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums) < 3: return False
         
         tails = [-float('inf')] + [float('inf')]*3
         for x in nums:
             for i in range(2, -1, -1):
                 if x > tails[i]:
                     tails[i+1] = x
                     break
             if tails[-1] < float('inf'):
                 return True
         return False

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         first = second = float('inf')
         for n in nums:
             if n <= first:
                 first = n
             elif n <= second:
                 second = n
             else:
                 return True
             print(n, first, second)
         return False

class Solution:
     def increasingTriplet(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if nums == [] :
             return(False)
         min = nums[0]
         sec_min = (2**31 -1 )
         
         for i in nums :
             if i <= min :
                 min = i
             else :
                 if i <= sec_min :
                     sec_min = i
                 else :
                     return(True)
         return(False)