# Share my solution in Increasing Triplet Subsequence with detail explanation.

• 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;
}
``````

};

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