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.