Java O(1) space O(n) time


  • -1
    Q
    public boolean increasingTriplet(int[] nums) {
             if(nums.length<3) return false;
    		 int min1 = Integer.MAX_VALUE;
    		 int min2 = Integer.MAX_VALUE;
    		 for (int i=1;i<nums.length;i++){
    			 if (nums[i]>nums[i-1]){
    				 if (nums[i]>min2)			 
    				    return true;
    				 else if (nums[i-1]<min1){
    					 min1 = nums[i-1];
    					 min2 = nums[i];
    				 }
    			 }
    	
    		 }
    		 return false;
    	 }

  • 0
    Q
    This post is deleted!

  • -1
    Q

    Modified code. Original was failing custom test case [2,5,3,4,5]

    public boolean increasingTriplet(int[] nums) {
         int min = Integer.MAX_VALUE;
    	 for (int i=1;i<nums.length;i++){
    	    if (nums[i]>min)	return true;
    		if (nums[i]>nums[i-1] && nums[i]<min)
    			 min = nums[i];
    	 }
    	 return false;
    }
    

    Modified again. Back to 2 variables, above one was failing newly added [5, 1, 5, 5, 2, 5, 4] test case

    public boolean increasingTriplet(int[] nums) {
         int min1 = Integer.MAX_VALUE;
         int min2 = Integer.MAX_VALUE;
         for (int i=1;i<nums.length;i++){
        	 if (nums[i]>min2) return true;
        	 else  if (nums[i]>min1 && nums[i]<min2)
        	    min2 = nums[i];
             else if (nums[i]>nums[i-1] && nums[i]<min2){
                min1 = nums[i-1];
        	    min2 = nums[i];
             }
         }
         return false;
    }
    
    
     The idea behind the solution. There must be 2 consecuitive incresing numbers somewhere 
      in the sequence otherwise the sequence is strictly flat or decreasing. Once we find the first 
      two numers where nums[i-1]<nums[i] we can keep looking for
      1. nums[k]>nums[i]. We are done if we find it.
      2. A number that's between them.  nums[i-1]<nums[k]<nums[i], therby increasing potential candiates for (1)
      3. Another two numbers where nums[k-1]<nums[k], and nums[k]<nums[i], therby increasing pontential candiates for (1)
    

  • 0
    Q

    Whey -1. Care to comment?


Log in to reply
 

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