Increasing Triplet Subsequence LeetCode Solution

Problem Statement :

Increasing Triplet Subsequence LeetCode Solution – 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.

Example :

Example 1:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Constraints :

Observation :

• In the given constraints length of the array can be 5 * 10^5, so the brute force solution O(n^2) or O(n^3) will not work here, we need to do something better than Brute force.
• We want  i < j < k and nums[i] < nums[j] < nums[k], if we try to make nums[i] as small as possible and also make  nums[j] smaller but nums[j] should be greater than nums[i] so it will help us.
• If we observe, the Greedy algorithm will work fine.

A variant of a longest increasing subsequence

• We need to maintain 2 variables x and y.
• x is the smallest number seen so far. x is also the smallest last number amongst all subsequences seen so far.
• If we take all increasing subsequences of size 2 and represent a subsequence as s[0], s[1]; then y is min(s[1]).
• For any new number z, if z is more than y, we have our solution.

Algorithm :

• Initialize two variables left and middle with Integer.MAX_VALUE (Integer MAXIMUM VALUE). 

int left=Integer.MAX_VALUE;

int middle=Integer.MAX_VALUE;

• Iterate from left to right in the nums array.

• While iterating try to find an element that follows the right > middle > left condition and name this element as right.

int right = nums[i];

• If the right is smaller than the left variable then make left = right.

• If the right is in between the left and middle then move middle to right place middle = right.

• If the right is greater than the left and middle then return true.
• After the end of the loop if we didn’t get the Increasing Triplet Subsequence then return false.

Code :

Java Code For Increasing Triplet Subsequence :

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n= nums.length;
        int left=Integer.MAX_VALUE;
        int middle=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int right=nums[i];
            if(right<left){
                left=right;
            }
            else if(right<middle && right > left){
                middle = right;
            }
            else if(right>middle&& right>left)return true;
        }
        return false;
    }
    
}

C++ Code For Increasing Triplet Subsequence :

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
         int n= nums.size();
        int left=INT_MAX;
        int middle=INT_MAX;
        for(int i=0;i<n;i++){
            int right=nums[i];
            if(right<left){
                left=right;
            }
            else if(right<middle && right > left){
                middle = right;
            }
            else if(right>middle&& right>left)return true;
        }
        return false; 
    }
};

Complexity Analysis for Increasing Triplet Subsequence LeetCode Solution :

Time Complexity :

O(N)

Space Complexity :

O(1) as we are not using any extra space.