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

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

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)