In this Leetcode Increasing Triplet Subsequence problem solution we have 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.

Leetcode Increasing Triplet Subsequence problem solution


Problem solution in Python.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3: return False
        seq = [None] * 3
        for num in nums:
            for j in range(3):
                if seq[j] is None or num <= seq[j]:
                    seq[j] = num
                    break
            if seq[2] is not None: return True
        return False



Problem solution in Java.

class Solution {
    public boolean increasingTriplet(int[] A) {
        
        int n  = A.length;
        int[] min = new int[n];
        int[] max = new int[n];
        
        min[0] = A[0];
        max[n-1] = A[n-1];
        for(int i=1,j;i<n;i++){
            j = n-i-1;
            min[i] = Math.min(min[i-1], A[i]);
            max[j] = Math.max(max[j+1], A[j]);
        }
        
        for(int i=1;i<n-1;i++){
            int l = min[i-1];
            int r = max[i+1];
            if(l< A[i] && A[i]<r) return true;
        }
        return false;
    }
}


Problem solution in C++.

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


Problem solution in C.

bool increasingTriplet(int* nums, int numsSize) {

if (numsSize < 3) return false;
int l = nums[0], m = 0x7fffffff;
for (int i = 1; i < numsSize; i++) {
    int a = nums[i];
    if (a <= l) l = a;
    else if (a < m) m = a;
    else if (a > m) return true;
}
return false;
}