8.Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Example 1:
Input: [1,2,3,4,5]
Output: true

Example 2:
Input: [5,4,3,2,1]
Output: false

Solution:

Approach: Keep track of two elements in the array min , and max. (min<max) If any time we find an element which is greater than max(Return True)

class Solution
{
public:
    bool increasingTriplet(vector<int> &nums)
    {

        if (nums.size() == 0)
        {
            return false;
        }

        int min = nums[0];
        int max = INT_MAX;

        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] > max)
            {
                return true;
            }

            if (nums[i] < min)
            {
                min = nums[i];
            }
            else if (nums[i] > min)
            {
                max = nums[i];
            }
        }

        return false;
    }
};

Time Complexity: O(n), Space Complexity: O(1)