334 Increasing Triplet Subsequence

334. Increasing Triplet Subsequence

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], returntrue.

Given[5, 4, 3, 2, 1], returnfalse.

2. Implementation

(1) DP

思路: 直接用Longest Increasing Subsequence的做法，如果最长的递增子序列长度大于等于3，则return true。如果遍历整个数组后，最长递增子序列都小于3，则返回false

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) {
            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] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }

                maxLen = Math.max(maxLen, dp[i]);
                if (maxLen >= 3) {
                    return true;
                }
            }
        }
        return false;
    }
}

(2) Linear Search

思路: 因为问题只问是否存在长度为3的increasing subsequence，我们可以维护两个变量min1, min2，min1表示当前在数组i的位置上最小的数，min2表示当前数组i的位置上次小的数，当我们从左向右扫描数组时，如果当前的数num符合min1 < min2 < num，则返回true

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)