Last updated on January 5th, 2025 at 01:01 am

Here, we see Increasing Triplet Subsequence LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array

Companies

Facebook

Level of Question

Medium

Increasing Triplet Subsequence LeetCode Solution

1. Problem Statement

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.

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Two Pointers”. The algorithm uses two variables (low and mid in C++, min and secondMin in Java, firstNumber and secondNumber in JavaScript, first and second in Python) to track the smallest and second smallest numbers encountered so far. These two variables act as pointers to help determine if there exists a triplet in increasing order.

3. Code Implementation in Different Languages

3.1 Increasing Triplet Subsequence C++

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

3.2 Increasing Triplet Subsequence Java

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
        for(int num : nums){
            if(num <= min) min = num;
            else if(num < secondMin) secondMin = num;
            else if(num > secondMin) return true;
        }
        return false;        
    }
}

3.3 Increasing Triplet Subsequence JavaScript

var increasingTriplet = function(nums) {
    let firstNumber = Infinity;
    let secondNumber = Infinity;
    for (let currentNumber of nums) {
        if (currentNumber > secondNumber && currentNumber > firstNumber) {
        return true;
        }
        if (currentNumber > firstNumber) {
        secondNumber = currentNumber;
        } else {
        firstNumber = currentNumber;
        }
    }
    return false;    
};

3.4 Increasing Triplet Subsequence Python

class Solution(object):
    def increasingTriplet(self, nums):
        first = second = float('inf')
        for n in nums:
            if n <= first:
                first = n
            elif n <= second:
                second = n
            else:
                return True
        return False

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)

• The algorithm is efficient because it avoids nested loops and uses a single pass through the array.
• The use of two pointers (low and mid) ensures that the solution is both time and space optimal.
• The algorithm works for any array size, but it immediately returns false if the array has fewer than 3 elements, as a triplet cannot exist in such cases.