# 334. Increasing Triplet Subsequence (Medium)

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

## Solutions

### 1.

``````class Solution {

// Firstly, Initialize the first and second element; Then, update the them if meets better alternatives;
// 3. Finally, return true if hit element > second.

public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length <= 2) {
return false;
}

int len = nums.length;

int first = nums;
int second = nums;

int i = 1;
for (; i < len; i++) {
if (nums[i] > first) {
second = nums[i];
break;
}

if (nums[i] < first) {
first = nums[i];
}
}

if (i >= len - 1) {
return false;
}

// Now, we get the sort a ascending pair (one, second). But I need to point out that it doesn't
// represent they will form the final answer.

// Move on to find the third element.
i++;

for (; i < len; i++) {
if (nums[i] > second) {
return true;
}

// to reach here, subject to nums[i] <= second and nums[i-1] <= second

// Here we have 3 jobs to do:

// 1. replace second only
if (nums[i] < second && nums[i] > first) {
second = nums[i];
continue;
}

// 2. replace one and second both, must cover = situation
// [5,6,1,6,2,3], [5,6,2,3]
if (nums[i - 1] <= first && nums[i] <= second && nums[i - 1] < nums[i]) {
first = nums[i - 1];
second = nums[i];
continue;
}

// 3. ignore nums[i]

// we cannot replace one with nums[i] because of the index sequence disorder issue
}

return false;
}
}
``````

### 2.

``````class Solution {

// This problem is too trivial and nasty. A great number of special cases need to be covered.

public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length <= 2) {
return false;
}

int len = nums.length;

int first = nums;
int second = Integer.MAX_VALUE;

int min = nums;

for (int i = 1; i < len; i++) {

// global minimum value
min = Math.min(min, nums[i]);

// if second is not assigned value yet
// [4,1,2], [1,3,4]
if (second == Integer.MAX_VALUE && nums[i] > nums[i - 1]) {
first = nums[i - 1];
second = nums[i];
continue;
}

// if (i-1, i) is a ascending pair
if (nums[i] > nums[i - 1]) {
// [1,5,3], (1,3) is better than (1,5)
if (nums[i - 1] > first && nums[i - 1] < second) {
second = nums[i - 1];
}
// min can be any values before i-1, so sequence min < nums[i - 1] < nums[i] meets
// the requirement.
else if (nums[i - 1] > min) {
return true;
}
// nums[i-1]<nums[i]<second, choose the minimums from both (first, nums[i-1])
// and (second, nums[i]).
else if (nums[i] < second) {
if (first < nums[i - 1]) {
second = nums[i - 1];
} else {
first = nums[i - 1];
second = nums[i];
}

// Following statements are incorrect. If first is set to nums[i-1], second
// must be nums[i]. Supposed second not change, index of second will be
// smaller than one.

// first = Math.min(first, nums[i - 1]);
// second = Math.min(second, nums[i]);
}
}

// To narrow down the search scale, no need to take the descending pair into account.

// one and second are already settled, if nums[i] > second, the ascending
// sequence of length 3 is found.
if (second != Integer.MAX_VALUE && nums[i] > second) {
return true;
}
}

return false;
}
}
``````

## Incorrect Solutions

``````class Solution {

// FIXME Incorrect Solution, extra space is not allowed.

// Apply a stack, walk through nums elements and push into elements smaller than
// the stack top, meanwhile pop out the larger value until current nums element can get in.
// Return directly if desired ans found.

public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length <= 2) {
return false;
}

// failed case [2,3,1,4]

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < nums.length; i++) {

// FIXME stack.peek() == nums[i] will still be popped.

while (!stack.isEmpty() && stack.peek() >= nums[i]) {
stack.pop();
}

stack.push(nums[i]);

if (stack.size() == 3) {
return true;
}
}

return false;
}
}
``````