# 334. 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.

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.

``````// Dumped, brute force
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
if (dp[i] >= 3) return true;
}
}
}
return false;
}
};
``````

``````class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int m1 = INT_MAX, m2 = INT_MAX;
for (auto a : nums) {
if (m1 >= a) m1 = a;
else if (m2 >= a) m2 = a;
else return true;
}
return false;
}
};
``````

nums:        8  3  5  1  6

foward:      8  3  3  1  1

backward:  8  6  6  6  6

``````class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if (nums.size() < 3) return false;
int n = nums.size();
vector<int> f(n, nums[0]), b(n, nums.back());
for (int i = 1; i < n; ++i) {
f[i] = min(f[i - 1], nums[i]);
}
for (int i = n - 2; i >= 0; --i) {
b[i] = max(b[i + 1], nums[i]);
}
for (int i = 0; i < n; ++i) {
if (nums[i] > f[i] && nums[i] < b[i]) return true;
}
return false;
}
};
``````