334. Increasing Triplet Subsequence

Description

The problem requires determining if there exists a strictly increasing subsequence of length 3 in a given array of integers, nums. A strictly increasing subsequence means that for any triplet of indices \( i < j < k \), we must have \( nums[i] < nums[j] < nums[k] \).

Intuition

To solve this problem, the key is to maintain two variables that capture the smallest and the second smallest elements encountered so far in the array. If we can find a third element greater than these two, then an increasing triplet exists. By iterating through the array and updating these two variables accordingly, we can efficiently determine if such a triplet exists.

Approach

1. Initialize two variables, prev1 and prev2, to infinity. These will store the smallest and second smallest values found so far, respectively.
2. Traverse the array. For each element: - If it is greater than prev2, then we have found a triplet where \( prev1 < prev2 < current\_element \), so return True. - If it is greater than prev1 but less than or equal to prev2, update prev2 to be this element. - If it is less than or equal to prev1, update prev1 to be this element.
3. If the loop completes without finding such a triplet, return False.

Complexity

Time Complexity:

( O(n) ), where ( n ) is the length of the input array. This is because we only traverse the array once.

Space Complexity:

( O(1) ), as we are using only a constant amount of extra space for the two variables prev1 and prev2.

Code

C++

class Solution {
public:
    bool increasingTriplet(vector& nums) {
        int prev1 = INT_MAX;
        int prev2 = INT_MAX;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > prev2 && prev2 > prev1) {
                return true;
            }

            if (nums[i] > prev1) {
                prev2 = nums[i];
            } else {
                prev1 = nums[i];
            }
        }

        return false;
    }
};

Python

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        prev1 = float('inf')
        prev2 = float('inf')

        for num in nums:
            if num > prev2 and prev2 > prev1:
                return True

            if num > prev1:
                prev2 = num
            else:
                prev1 = num

        return False

Java

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int prev1 = Integer.MAX_VALUE;
        int prev2 = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > prev2 && prev2 > prev1) {
                return true;
            }

            if (nums[i] > prev1) {
                prev2 = nums[i];
            } else {
                prev1 = nums[i];
            }
        }

        return false;
    }
}

JavaScript

var increasingTriplet = function (nums) {

    let prev1 = Infinity;
    let prev2 = Infinity;
    let isIncreasingTriplet = false;

    for (var indexI = 0; indexI < nums.length; indexI++) {
        
        if (nums[indexI] > prev2 && prev2 > prev1) {
            isIncreasingTriplet = true;
            break;
        }

        if (nums[indexI] > prev1) prev2 = nums[indexI];
        else prev1 = nums[indexI];
    }
    return isIncreasingTriplet;
};