bool increasingTriplet(vector<int>& nums) {
int c1 = INT_MAX, c2 = INT_MAX;
for (int x : nums) {
if (x <= c1) {
c1 = x; // c1 is min seen so far (it's a candidate for 1st element)
} else if (x <= c2) { // here when x > c1, i.e. x might be either c2 or c3
c2 = x; // x is better than the current c2, store it
} else { // here when we have/had c1 < c2 already and x > c2
return true; // the increasing subsequence of 3 elements exists
}
}
return false;
}
Clean and short, with comments, C++


Your solution is just to keep a window of size=3, and keep updating the c1 and c2 just like the LIS(longest increasing sequence) Problem. but we know the size=3, so we need do not need to use the binary search to find the updating position, so we can do it in O(N).
You can see me LIS solution inhttps://leetcode.com/discuss/87255/justusingthelistosolvetheproblemin8ms

The approach is simple: Continuously update the range covered by 2 numbers represented by A[0] & A[1]. Initially they are initialized by INT_MAX and we keep lowering their values. If anytime we find a number larger than A[1], return true.
class Solution { public: bool increasingTriplet(vector<int>& x) { int A[2] = {INT_MAX, INT_MAX}; if (x.size() < 3) return false; for (int i = 0; i < x.size(); i++) { if (x[i] < A[0]) A[0] = x[i]; else if (x[i] > A[0] && x[i] < A[1]) A[1] = x[i]; else if (x[i] > A[1] && x[i] <= INT_MAX) return true; else continue; } return false; } };

class Solution { public: bool increasingTriplet(vector<int>& nums) { int len=nums.size(); int a[3]; int pos=1; for(int i=0;i<len;i++) { if(pos==1nums[i]>a[pos]) { a[++pos]=nums[i]; if(pos==2) return true; } else { if(nums[i]<a[0]) a[0]=nums[i]; else if(pos==1&&nums[i]>a[0]&&nums[i]<a[1]) a[1]=nums[i]; } } return false; } };

before coding I also thought about this solution and I did’t think that will work, as it appears to be very naïve and greedy: find first smallest, then find second smallest, then find the third and bingo. I argued myself it cannot pass the case like [1,2,0,3] since c1 is changed.
But when I take a closer look, it does [1,2,0,3] very well. And I realize that c1 and c2 are indeed having the meaning of:
C1 = so far best candidate of end element of a onecell subsequence to form a triplet subsequence
C2 = so far best candidate of end element of a twocell subsequence to form a triplet subsequence
So c1 and c2 are the perfect summary of history.
public class Solution { public boolean increasingTriplet(int[] nums) { int c1 = Integer.MAX_VALUE, c2 = Integer.MAX_VALUE; for (int i : nums) if (i <= c1) c1 = i; else if (i <= c2) c2 = i; else return true; return false; } }

@jedihy, I don't think the posted method is naive. You are right, its the same method as in LIS.



@alveko FYI  wow the simplicity of this approach is awesome!
I came up with this, which is way less awesome but more how you might try it by hand (which is how I stumbled into it's trap!).
As you iterate your array you want to keep the "best" increasing pair, which is the pair with the lowest top value. Of course if you find a value above the top of your pair you're done, a value between the pair you just update the top end. Now if the value is less than your low end you need to hold it until you find another also lower than your low end but above this held value. Once you find this you have a new "best" pair.
Of course when you go to code this it does not look so pretty and of course is not nearly as slick as when you just realize you can get away with only keeping the last 2.
One advantage I would say though is that if you needed to actually produce the indexes for the triplet you would actually need something like below.
Thanks!
public class Solution { public bool IncreasingTriplet(int[] nums) { Doublet doublet = new Doublet(); for (int i = 0; i < nums.Length; i++) { if (doublet.Check(nums, i)) return true; } return false; } } public class Doublet { public int index1 = 1; public int index2 = 1; public int indexNext = 1; public bool Check(int[] arr, int i) { if (index1 != 1 && index2 != 1 && arr[i] > arr[index2]) { // found return true; } if (index1 == 1  (arr[i] <= arr[index1] && index2 == 1)) { // new 1 index1 = i; } else if (index2 == 1  (arr[i] > arr[index1] && arr[i] < arr[index2])) { // new 2 index2 = i; } else if (arr[i] < arr[index1]) { if (indexNext == 1  arr[i] < arr[indexNext]) { // new overall min  hold indexNext = i; } else if (arr[i] > arr[indexNext] && arr[i] <= arr[index1]) { // new pair  promote index2 = i; index1 = indexNext; indexNext = 1; } } // not found return false; } }