Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

The inituation behind the optional solution is to undstand that:

• We must traverse though the list just once.
• We keep track 2 pointers, firstValue and secondValue
• firstValue is updated if we come across a value nums[i] such that nums[i]<= firstValue.
• secondValue is updated only if it is larger then firstValue and nums[i] <= secondValue
• If we come to a value nums[i] such that it is larger then both firstValue and secondValue, we immediately return true since we have found a index i, j, k such that nums[i] < nums[j] < nums[k]

firstValue and secondValue can be conveniently set to MAX INT to start off. This guarantees that firstValue will be set to num[0] to start off. As we traverse down the list, secondValue will only be set of it is larger then firstValue. Otherwise firstValue will be updated.

class Solution {
    public boolean increasingTriplet(int[] nums) {
     
        if (nums.length < 3) {
            return false;
        }
          
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;      
        
        for (int i=0; i<nums.length; i++) {
            int currentValue = nums[i];
            if (currentValue <= first) {
                first = currentValue;
            } else if (currentValue <= second) {
                second = currentValue;
            } else {
                return true;
            }                    
        }
        
        return false;
    }
}

Conclusion

The examples that are presented along with the question are very important. It is very common for candidates to make the mistake that i, j and k must be subsequent positions one after each other (i.e. i, j = i + 1, and k = i + 2).