# LeetCode 334. Increasing Triplet Subsequence

## Description

https://leetcode.com/problems/increasing-triplet-subsequence/

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.

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

Example 1:

```Input: [1,2,3,4,5]
Output: true
```

Example 2:

```Input: [5,4,3,2,1]
Output: false```

## Explanation

Forward to create a list of the smallest number at each index position. Backward to create a list of the greatest number at each index position. If any number at same index greater than the number in forward, and smaller than the number in backward, then a triplet found.

## Python Solution

``````class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
if len(nums) < 3:
return False

forward = []
backward = []

forward.append(nums)

for i in range(1, len(nums)):
num = nums[i]
if num < forward[i - 1]:
forward.append(num)
else:
forward.append(forward[i - 1])

backward.append(nums[len(nums) - 1])
for i in range(1, len(nums)):
num = nums[len(nums) - i - 1]
if num > backward[i - 1]:
backward.append(num)
else:
backward.append(backward[i - 1])

backward.reverse()

for i in range(0, len(nums)):
num = nums[i]
if backward[i] > num > forward[i]:
return True

return False``````
• Time complexity: O(N).
• Space complexity: O(N).