Share my solution in Increasing Triplet Subsequence with detail explanation.


  • 1
    Y

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

    };


Log in to reply
 

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