Greedy: Check for Increasing triplet subsequence

Problem Statement:

You are given an array, you need to return true, if there is triplet in increasing subsequence.

Example:

Input: arr = [1, 2, 3, 4]

Output: Yes

Explanation: [1, 2, 3] is a increasing subsequnce

Solution Explanation:

We will take 2 variables num_1 and num_2 initialize to Int_Max.

Then iterate through the array, if the element is less than equal to num_1, update num_1.

Then if the element is greater than num_1 and less then num_2, then update num_2.

Then if the element is greater than num_1 and num_2, then return true, if no such element exist, then return false.

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

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

bool solution(vector<int>& nums) 
{
    if (nums.size() < 3) 
    {
        return false;
    }

    int num_1 = INT_MAX;
    int num_2 = INT_MAX;

    for (int num : nums) 
    {
        if (num <= num_1) 
        {
            num_1 = num;
        } 
        else if (num <= num_2) 
        {
            num_2 = num;
        } 
        else 
        {
            return true;
        }
    }

    return false;
}

int main() 
{
    vector<int> arr = {1, 2, 3, 4};

    if(solution(arr))
    {
    	cout<<"True";
    }
    else 
    {
    	cout<<"False";
    }
    return 0;
}

Output

True