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.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def increasingTriplet(self, nums):
		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):
		(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):
		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):
		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):
		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):
		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):
		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):
		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):
		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):
		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):
		if nums == []:
			return False
		min = nums[0]
		sec_min = 2 ** 31 - 1
		for i in nums:
			if i <= min:
				min = i
			elif i <= sec_min:
				sec_min = i
			else:
				return True
		return False