My accepted JAVA solution for this question, only 7-lines, clear and concise.


  • 50
    B

    The main idea is keep two values when check all elements in the array: the minimum value min until now and the second minimum value secondMin from the minimum value's position until now. Then if we can find the third one that larger than those two values at the same time, it must exists the triplet subsequence and return true.

    What need to be careful is: we need to include the condition that some value has the same value with minimum number, otherwise this condition will cause the secondMin change its value.

    public class Solution {
        public boolean increasingTriplet(int[] nums) {
            int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
            for(int num : nums){
                if(num <= min) min = num;
                else if(num < secondMin) secondMin = num;
                else if(num > secondMin) return true;
            }
            return false;
        }
    }
    

    The running time complexity is O(n).


  • 0
    E

    very clean and elegant solution~~~~


  • 5
    C

    Clarification in the exp: the two values should be:

    1. the min value
    2. the smallest second value: the smallest value that has something before it that is even smaller. That 'something before it that is even smaller' does not have to be the current min value.

    Example:
    3,2,1,4,0,5

    When you see 5, min value is 0, and the smallest second value is 4, which is not after the current min value.

    Your implementation is correct.


  • 4
    X

    I don't think it is correct when solving the array{5,2,4,1,5,2,2}

    1.5<min(this time min=integer.maxvlaue)
    so min=5

    2.2<min
    so min = 2

    3.4>min but 4<secondmin
    so secondmin =4

    4.1<min
    so min=1(that is the error occured,because the correct triplet subsequence is 2,4,5)

    5.5>secondmin
    return true

    so the result is
    min = 1 secondmin=4 third =5

    but actually 1 appears behind 4,so 1,4 is violate the increasing triplet subsequence.

    the correct subsequence is {2,4,5}


  • 3
    B

    In your example, the result becomes true when the second 5 comes in, at this moment the min =1, secondMin =4, which "seems" violate the increasing triplet subsequence rule.

    But what I need get is just the boolean value true or false, which means I only wants to know whether there exists an increasing triplet subsequence . So, in your example [5,2,4,1,5,2,2] when the first 1 has been added, it updates the min value of course, but it has no influence on the result because there must exists an element next that larger than the secondMin value to make the result to be true. In this case is 5>4. So although the min and secondMin is not exactly the increasing triplet subsequence's element, the boolean result still can be right.


  • 0
    W

    Any solution to find the triplet indexes when return true?
    This solution can't find correct indexes in fact.


  • 0
    X

    well,I still don't really understand why it is always return right boolean value.But,exactly it seems like that.


  • 0
    Y

    @billleeforfun You guys always open a new world to me . So brilliant.


  • 2
    S

    @xiaopeizhi

    • Basic Idea:
      Record a 'first' and 'second' which indicate a length-2 increasing subsequence we've found so far.
      Record a 'min' which indicates the smallest number in the array so far, but the 'min' might not be in a length-2 increasing subsequence.
      Traverse the array and update those records, until we reach the end or find a number greater than 'second'.

    • Improved Idea (billleeforfun's idea):
      We don't need the 'first'. Since a third number in the increasing subsequence is greater than 'second', it is, of course, greater than some 'first' which appears before 'second'. We don't care whether that 'first' is identical to the 'min' or not. In this way, we don't have to keep record of the 'first'

    @xiaopeizhi said in My accepted JAVA solution for this question, only 7-lines, clear and concise.:

    well,I still don't really understand why it is always return right boolean value.But,exactly it seems like that.


  • 1
    G

    Really smart solution, though the return indexes for the subsequence are wrong. The basic idea is that the SecondMin value will be updated only if there is at least one smaller value before it.


  • 0
    G

    But what if you want to extend this problem to length 'n' instead of 3? What kind of a data structure would make this code robust?

    It feels hard coding two variables is reducing the potential of this logic. Just thinking loud. Please ignore if it is not relevant.

    BTW, really elegant solution!! Good one..


  • 0
    P
    This post is deleted!

  • 0
    D

    The solution can be approved logically right. But what if the requirement becomes, return this triplet?


  • 0
    This post is deleted!

  • 0

    @www2277843987 @darrenxyli my triplet solution

    If return true the triplet is <first, second, nums[i]>

    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 1) return false;
        int min = nums[0], first = min, second = min;
        int index = 1;
        for (int i = 0; i < nums.length; i++) {
            if (index == 1) {
                if (nums[i] <= first) {
                    first = nums[i];
                    min = first;
                } else {
                    second = nums[i];
                    index++;
                }
            } else {
                if (nums[i] > second) return true;
                else if (nums[i] <= min) {
                    min = nums[i];
                } else {
                    first = min;
                    second = nums[i];
                }
            }
        }
        return false;
    }
    

  • 0
    C

    Could use an extra variable to store the matching min for secondMin, then for test case [5,2,4,1,5,2,2], the result increasing triplet subsequence would be [2,4,5] instead of[1,4,5]

    public boolean increasingTriplet(int[] nums) {
            int min = Integer.MAX_VALUE, firstMin = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
            for(int num : nums){
                if(num <= min) min = num;
                else if(num < secondMin) { secondMin = num; firstMin = min; }
                else if(num > secondMin) { 
                    //System.out.print(firstMin + " " + secondMin + " " + num); 
                    return true; }
            }
            return false;
        }
    

  • 0
    C

    so clean and brilliant, thanks for sharing


  • 0
    C

    @CorvetteC6R I don't think it will need an extra variable for memorizing the matching min for secondMin, cause by using this method. it will find true or false for if there's a solution in this array. and cleaner.


  • 0
    G

    @xiaopeizhi you should think why it did like this,the real result is not the min,second min,big


Log in to reply
 

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