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.

Thinking:

We need to implement this algorithm in linear time and constant space. So we need to scan this array once and record the information needed in one time. We need to variable to record the information, the first one is the minimum of this array, and the second one is the number which is bigger than its previous elements. If one element is bigger than it, the result will be true. Otherwise, we should update the two variables’ values.

Solution:

public boolean increasingTriplet(int[] nums) {
    int l = nums.length;
    if (l < 3)    return false;
    int min = nums[0];
    int secmin = Integer.MAX_VALUE;

    for (int i = 1; i < l; i++) {
        if (nums[i] > secmin)    return true;
        else if (nums[i] <= min) min = nums[i];
        else if (nums[i] < secmin)    secmin = nums[i];
    }
    return false;
}