334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        //O(nlogn) with multiset
        if(nums.size() <= 2) return false;
        multiset<int> left{nums[0]}, right(nums.begin() + 2, nums.end());

        for(int i = 1; i <= nums.size() - 2; i++) {
            int J = nums[i];
            bool hasI = left.lower_bound(J) != left.begin();
            bool hasK = right.upper_bound(J) != right.end();
            if(hasI and hasK) return true;
            left.insert(J);
            right.erase(right.find(J));
        }

        return false;
    }
};

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        //O(n) with greedy
        if(nums.size() <= 2) return false;
        int first = INT_MAX, second = INT_MAX;
        
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] <= first) first = nums[i];
            else if(nums[i] <= second) second = nums[i];
            else return true;
        }

        return false;
    }
};