334. Increasing Triplet Subsequence (Medium)

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.

Solution 1: DP O(n); O(1)

    /**
     * DP O(n); O(1)
     * Similar to find two minimum values.
     * The only difference is we don't update second min when first min is found.
     * Otherwise n2 can be before n1, which is wrong.
     * So for each number n in nums:
     * | If n <= n1, update n1, that is the minimum.
     * | Else if n <= n2, update n2, that is the minimum after n1.
     * | Else, we find the third value, return true.
     * Return false if third value is not found.
     * Think it like we are filling three spaces.
     * The first space is the minimum.
     * When the first space is found, try to fill the second space.
     * If both are filled, when third space is filled, return true.
     */
    public boolean increasingTriplet(int[] nums) {
        if (nums == null) {
            return false;
        }

        int min = Integer.MAX_VALUE;
        int secondMin = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num <= min) {
                min = num;
            } else if (num <= secondMin) {
                secondMin = num;
            } else {
                return true;
            }
        }
        return false;
    }