# 334 Increasing Triplet Subsequence

## 334. [Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/description/)

## 1. Question

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

## 2. Implementation

**(1) DP**

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && (1 + dp[j] > dp[i])) {
                    dp[i] = 1 + dp[j];
                }
            }

            if (maxLen < dp[i]) {
                maxLen = dp[i];
            }
        }
        return maxLen >= 3;
    }
}
```

**(2) Linear Search**

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }

        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num <= min1) {
                min1 = num;
            } 
            else if (num <= min2) {
                min2 = num;
            }
            else {
                return true;
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n^2), 空间复杂度O(n)

**Linear Search:** 时间复杂度O(n), 空间复杂度O(1)