Leetcode: 334. Increasing Triplet Subsequence

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.

Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Understand the problem:
The easiest solution for this problem is to use the same DP method for the Longest Increasing Subsequence (LIS). If then, we only need to check if the dp[i] >= 3. However, this will result in a O(n^2) time complexity. Since this problem asks for O(n) time, we need to think another solution. 

The idea of the O(n) time solution is greedy. We maintain two variables m1 and m2, which denote the minimum number and next to minimum number we have seen so far. So for each number in the array, we update the minimum and next minimum. If the number if greater than both m1 and m2, then we found the increasing triplet. 

Code (Java):

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        
        int m1 = Integer.MAX_VALUE;
        int m2 = Integer.MAX_VALUE;
        
        for (int num : nums) {
            if (num <= m1) {
                m1 = num;
            } else if (num <= m2) {
                m2 = num;
            } else {
                return true;
            }
        }
        
        return false;
    }
}