Increasing Triplet Subsequence

Problem

Increasing Triplet Subsequence

Intuition

There are requirements about the time & space, O(n) time complexity and O(1) space complexity. So, we can use two variables to record the first minimal and second minimal element and stop when found the third one bigger than the second.

Code

// first version
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int[] ans = new int[3];
        for(int i = 0; i < ans.length; i ++)
            ans[i] = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i ++){
            if(ans[0] == Integer.MIN_VALUE) ans[i] = nums[i];
            else{
                if(ans[1] == Integer.MIN_VALUE){
                    if(nums[i] > ans[0]) ans[1] = nums[i];
                    else ans[0] = nums[i];
                }
                else{
                    if(ans[2] == Integer.MIN_VALUE){
                        if(nums[i] > ans[1]) return true;
                        else {
                            if(nums[i] > ans[0]) ans[1] = nums[i];
                            else{
                                ans[0] = nums[i];
                                // ans[1] can't be reset.
                                // here, it's my first error.
                                //ans[1] = Integer.MIN_VALUE;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
}

// clean code
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums.length < 3) return false;
        int f = nums[0], s = Integer.MAX_VALUE;
        for(int i = 1; i < nums.length; i ++){
            int t = nums[i];
            if(t > s) return true;
            if(t > f) s = t;
            else f = t;
        }
        return false;
    }
}