Concise Java solution with comments.


  • 152
       public boolean increasingTriplet(int[] nums) {
            // start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true.
            int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
            for (int n : nums) {
                if (n <= small) { small = n; } // update small if n is smaller than both
                else if (n <= big) { big = n; } // update big only if greater than small but smaller than big
                else return true; // return if you find a number bigger than both
            }
            return false;
        }

  • 2
    L

    brilliant idea!


  • 0
    P

    nice explanation


  • 0
    E

    Very brilliant solution!! Thanks for sharing


  • 1
    T

    Brilliant idea. But I am not clear how it works.
    Can you please explain some theory behind this...


  • 6
    H

    @TechPrep read the comments. they are pretty detailed.
    Starting from left to right, the numbers could lie in range [-----] for any small<big<thirdvalue
    -----small< -----big< -----thirdvalue

    a) if currentelement is less than small : update small to currentelement now the range for big can expand between new small and big
    b) if currentelement is between small and bigand less than current big : update big to currentelement now the range for thirdvalue can be any number greater than big
    c) if currentelement is greater than big: we found 3 such values return true


  • 7

    I would like to point out that for [1, 3, 0, 5] we will eventually arrive at big = 3 and small = 0 so big may come after small

    However, the solution still works, because big only gets updated when there exists a small that comes before it.


  • 13

    @皮皮鲁 This is the very case that confused me when I first read OPs solution. The logic is rather terse but works for such inputs. In case anyone else is reading and would like a further elaboration:

    initial : [1, 2, 0, 3], small = MAX, big = MAX
    loop1 : [1, 2, 0, 3], small = 1, big = MAX
    loop2 : [1, 2, 0, 3], small = 1, big = 2
    loop3 : [1, 2, 0, 3], small = 0, big = 2 // <- Uh oh, 0 technically appeared after 2
    loop4 : return true since 3 > small && 3 > big // Isn't this a violation??

    If you observe carefully, the moment we updated big from MAX to some other value, that means that there clearly was a value less than it (which would have been assigned to small in the past). What this means is that once you find a value bigger than big, you've implicitly found an increasing triplet.


  • 0
    F

    Brilliant idea!!
    The basic condition is at any time, small < big.
    So for any arbitrary element later, we call it i, there are three possibilities:
    a). i <= small < big, then just update small, and it will not change our basic condition, which is small < big.
    b). small < i <= big, then just update big. small < big still exists.
    c.) small < big < i, then we find a increasing triplet subsequence.


  • 0
    G

    small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;

    What an amazing idea!!!!
    I know to update minimal and second minimal number, but I'm stuck with initializing the two numbers! Briliant idea to set them as MAX_VALUE!


  • 0
    B

    brilliant idea


  • 0
    P

    "so good", after thinking through the theory behind the code.


  • 0
    P

    @FelixGEEK
    Not quite like how you explain.
    Think about [3, 4, 2, 1, 5], 5 is the element we want, but at the time we reach 5, small = 1, big = 4. But the sequence is not 1 4 5, it's 3 4 5.
    So I think here the condition is, if you find any element greater than big, it can be regarded as the third element in sequence. But in order to update the big variable, to give you bigger range for the third element, you need to update the small variable, which gives you bigger range for the new "big" variable.


Log in to reply
 

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