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;
}
Concise Java solution with comments.


@TechPrep read the comments. they are pretty detailed.
Starting from left to right, the numbers could lie in range [] for anysmall
<big
<thirdvalue
small
< big
< thirdvalue
a) if
currentelement
is less thansmall
: updatesmall
tocurrentelement
now the range forbig
can expand between newsmall
andbig
b) ifcurrentelement
is betweensmall
andbig
and less than currentbig
: updatebig
tocurrentelement
now the range forthirdvalue
can be any number greater thanbig
c) ifcurrentelement
is greater thanbig
: we found 3 such valuesreturn true

@皮皮鲁 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 after2
loop4 : returntrue
since3 > small && 3 > big
// Isn't this a violation??If you observe carefully, the moment we updated
big
fromMAX
to some other value, that means that there clearly was a value less than it (which would have been assigned tosmall
in the past). What this means is that once you find a value bigger thanbig
, you've implicitly found an increasing triplet.

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.

@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.