class Solution {

public:

bool increasingTriplet(vector<int>& nums) {

```
// principle: when we consider k+1 th num,
// we want to consider the pair with the smallest possible
// second value in the first k num.
// Consider the following test cases:
// 1. [2, 5, 3, 4, 6]
// 2. [2, 3, 1, 2, 3]
// 3. [2, 3, 1, 4]
if (nums.size() < 3) return false;
int min_in_k = nums[0];
int second = numeric_limits<int>::max();
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > second) return true;
// Here we guarantee we have the smallest possible second value.
else if (nums[i] < second && nums[i] > min_in_k) {
second = nums[i];
}
// Here we actually have only two cases:
// i. When first value in the pair is the min_in_k.
// ii. When first value in the pair is smaller the min_in_k.
// For i), that is exactly what we want.
// For ii), this doesn't really matter. Like test case 3,
// when considering 1, we still have the second value as 3.
// We didn't change the second value, which means, there is a
// first value that can be paired with the second. (satisfying
// the condition right above). If we have test case 2, we change
// min to 1, but at this time we don't have a second value paired
// with 1, so we keep using the previous pair. But when considering
// the next 2, we formed a new pair (1, 2) which replaces (2, 3).
// In summary:
// The key part is to beat the current second (the smallest second in
// the first k.)
// When we see a new value, we can either beat "the second" and win,
// or can at least form a new pair with a smaller, better second.
// For the "or" point, we should renew min to do so.
else if (nums[i] < min_in_k) {
min_in_k = nums[i];
}
}
return false;
}
```

};