IncreasingTripletSequence.java

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) return false; 
        int small = Integer.MAX_VALUE, mid = Integer.MAX_VALUE; 
        
        // invariant 1: both small and mid can only go down
        // invariant 2: mid will always greater than smaller
        // ==> If find a number greater than both, true
        for (int n : nums) {
            if (n <= small) { // Find a better small 
                small = n;  
            } else if (n <= mid) {  // Find a better mid, small larger than small
                mid = n;  
            } else { // Greater than mid (must also greater than mid), find a solution
                return true; 
            }
        }
        
        return false; 
    }
}