Simple Java O(n) time O(1) space solution


  • 1
    Z

    The idea is simple. Traversing the array from left to right, just store minimum number so far. If the number is greater than the minimum, then store minimum of the differences (smalles number that is greater than minimum). Then each time we meet number that is greater than the minimum one, compare its their difference with the stored minimum difference. If the the difference is greater than the store minimum difference so far, we have found an increasing triplet.

    P.S: do not forget to update the minimum difference when updating the minimum number.

    public class Solution {
        public boolean increasingTriplet(int[] nums) {
            if(nums.length < 3) return false;
            int min = nums[0];
            long diff = Integer.MAX_VALUE;
            for(int i =  1;i<nums.length;i++){
                if(nums[i]>min){
                    if(nums[i]-min > diff) return true;
                    diff = nums[i]-min;
                    continue;
                }
                int d = min - nums[i];
                diff+=d;
                min = nums[i];
            }
            return false;
        }
    }

Log in to reply
 

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