Increasing Triplet Subsequence - Leetcode Solution

The Increasing Triplet Subsequence problem on LeetCode can be solved using a simple dynamic programming approach.

The problem statement is as follows:

Given an unsorted array of integers, find if there is any increasing triplet subsequence.

A subsequence is defined as a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Solution:

The idea behind this solution is to keep track of the smallest two numbers seen so far and to check if there is a third number greater than these two that has been seen.

We can initialize two variables, named min and second_min, to store the smallest two numbers seen so far. We then iterate through the array and check if the current number is smaller than min. If yes, we update min. If the current number is greater than min but smaller than second_min, we update second_min. If the current number is greater than second_min, we have found an increasing triplet subsequence and we return true.

Here's the code written in Python:

def increasingTriplet(nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    min_num = float('inf')
    second_min_num = float('inf')
    
    for num in nums:
        if num <= min_num:
            min_num = num
        elif num <= second_min_num:
            second_min_num = num
        else:
            return True
    
    return False

Time Complexity: O(n), where n is the length of the input array.

Space Complexity: O(1), as we are only using two variables to store the smallest two numbers seen so far.

Sample Input/Output:

Input: [1,2,3,4,5] Output: True (as 1,2,3 is an increasing triplet subsequence)

Input: [5,4,3,2,1] Output: False (as no increasing triplet subsequence can be found)

Input: [2,4,-2,-3] Output: True (as -2,-3,2 is an increasing triplet subsequence)

1