[2018-Interview] Increasing Triplet Subsequence

Original question: https://leetcode.com/problems/increasing-triplet-subsequence/description/

Got answers from Jiuzhang:

Answer 1: O(n) time, O(1) space

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int[] preNums = new int[2];
        preNums[0] = nums[0];
        preNums[1] = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] <= preNums[0]) {
                preNums[0] = nums[i];
            } else if (nums[i] <= preNums[1]) {
                preNums[1] = nums[i];
            } else {
                return true;
            }
        }
        return false;
    }
}

Answer 2: O(n) time, O(n) space

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

// O(n) memory, if you want O(1)memory take a look at the c++ version
public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 2)
            return false;
        int n = nums.length;
        boolean []has_first_small = new boolean[n];
        int smallest = nums[0];
        has_first_small[0] = false;
        for (int i = 0; i < n; i ++) {
            if (smallest < nums[i]) {
                has_first_small[i] = true;
            }
            smallest = Math.min(smallest, nums[i]);
        }
        
        int biggest = nums[n-1];
        for (int i = n-2; i >=0; i--) {
            if(has_first_small[i] == true) {
                if (nums[i] < biggest) {
                    return true;
                }
                biggest = Math.max(biggest, nums[i]);
            }
        }
        return false;
    }
}