Share my O(n) Java solution (inspired by Longest Increasing Subsequece O(nlgn) solution)


  • 2
    M
    /*
        this is only a special case in "Longest Increasing Subsequence O(nlgn) solution"
        where the length of "min ending here" sequence is at most 3.
        
        in other words, we only need to consider:
        minimum ending of LIS whose length is 1, and
        minimum ending of LIS whose length is 2
    */
    public class Solution {
        public boolean increasingTriplet(int[] nums) {
            int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
            for (int num: nums) {
                if (num <= first) {  // update the minimum ending of LIS whose length is 1
                    first = num;
                } else if (num <= second) {  // update the minimum ending of LIS whose length is 2
                    second = num;
                } else {  // now first < second < num, num maybe the minimum ending of LIS whose length is 3
                    return true;
                }
            }
            return false;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.