# Increasing Triplet Subsequence LeetCode Solution

Difficulty Level Medium
RazorpayViews 18

## 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 == 0 < nums == 4 < nums == 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, s; then y is min(s).
• 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 :

O(N)

### Space Complexity :

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

Translate »