Concise Java solution with comments.


  • 148
    S
       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...


  • 4
    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


  • 3

    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.


  • 7

    @皮皮鲁 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


Log in to reply
 

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