LeetCode Challenge #334. Increasing Triplet Subsequence

Day 18 of 100 Days LeetCode Challenge

Question 8 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #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.

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

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

Example 3:

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.

Constraints:

1 <= nums.length <= 5 * 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Java Video Solution

C++ Video Solution

Java Solution

				
					class Solution {
    public boolean increasingTriplet(int[] nums) {
       int first = Integer.MAX_VALUE ;
       int second = Integer.MAX_VALUE ;
       int third = Integer.MAX_VALUE ;

       for(int i=0;i<nums.length;i++){

           int ele= nums[i];
           if(first>=ele){
               first = ele ;
           }else if ( second >= ele){
               second = ele ;
           }else {
               third = ele ;
               return true ;
           }
       }
       return false ;
    }
}

C++ Solution

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

Code Explanation

In this program, we have to reverse the order of words, but keeping the word’s direction in the same way. Only the words will be interchanged.

In this program, the goal is to find out if there are three numbers in this list such that one is smaller than the other and the other is smaller than the next. Then we call this an “increased triplet subsequence.”
An increasing triplet subsequence is a set of three numbers (i, j, and k) such that ‘nums(i) < nums(j) < nums(k).

Let’s see the approach step-by-step:

According to our given condition, the rightmost element should be the maximum one, which means if we move from left to right and find the maximum element, then the previous two elements will be the middle one and the smallest one.

For this purpose, we will initialise two variables as ‘smallest’ and ‘middle’, both set to INT_MAX. For keeping track of the smallest and second-smallest elements encountered so far.

We also check if the size of the vector is less than 3. If the size is less than 3, there can’t be an increasing triplet subsequence, so the function immediately returns ‘false’.

Now, let’s start the ‘for’ loop that will iterate through each element in the vector ‘nums’.

Inside the loop, it checks three conditions:

If the current number is greater than the “middle” number it has seen so far, then it finds an increasing triplet, and it says “yes”.

If the current number is between the smallest and the middle number, it updates the middle number, because we found a potential second smallest element.

If the current element is less than ‘smallest’ , it updates ‘smallest’ to the current element. This is because we found a new smallest element.

Now, finally ,If the loop completes without finding an increasing triplet subsequence, the function returns ‘false’.

Day 18 of 100 Days LeetCode Challenge

Question 8 of 75 - LeetCode Weekly Challenge