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^5 -2^31 <= nums[i] <= 2^31 - 1

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

## Increasing Triplet Subsequence

This problem asks us to find if there exists a subsequence of length 3 in an array such that the elements in the subsequence are strictly increasing. We'll start with a brute-force approach and then optimize it to achieve O(n) time complexity.

### 1. Brute-Force Approach

The most straightforward approach is to check every possible triplet of indices (i, j, k) such that i < j < k and see if `nums[i] < nums[j] < nums[k]`. This approach is easy to understand but not efficient.

```python
def increasingTriplet_bruteForce(nums):
    n = len(nums)
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if nums[i] < nums[j] < nums[k]:
                    return True
    return False

2. Optimal Approach

To achieve O(n) time complexity, we can use two variables to keep track of the smallest and second smallest numbers seen so far.

def increasingTriplet(nums):
    if len(nums) < 3:
        return False
    
    smallest = float('inf')
    second_smallest = float('inf')
    
    for num in nums:
        if num <= smallest:
            smallest = num  # Update smallest if we find a smaller number
        elif num <= second_smallest:
            second_smallest = num  # Update second smallest if we find a number between smallest and second smallest
        else:
            return True  # We found a number greater than both smallest and second smallest
    
    return False

Explanation:

• Initialize smallest and second_smallest to infinity.
• Iterate through the array.
  • If the current number is smaller or equal to smallest, update smallest.
  • Else, if the current number is smaller or equal to second_smallest, update second_smallest.
  • Else, it means we have found a number greater than both smallest and second_smallest, which means we have an increasing triplet. Return True.
• If we finish iterating through the array without finding such a triplet, return False.

3. Big(O) Time Complexity Analysis

The optimal approach iterates through the array once, performing constant-time operations in each iteration. Therefore, the time complexity is O(n), where n is the length of the input array.

• O(n): Single pass through the array.

4. Big(O) Space Complexity Analysis

The optimal approach uses only two variables (smallest and second_smallest) to keep track of the minimum values. Therefore, the space complexity is O(1), which means constant space.

• O(1): Constant space used regardless of the input size.

5. Edge Cases

1. Empty Array or Array with Less Than 3 Elements:
   • The function should return false since an increasing triplet is not possible.
2. Array with Duplicate Elements:
   • The algorithm should still work correctly because we are looking for a strictly increasing subsequence.
3. Array with All Elements in Descending Order:
   • The function should return false as there is no increasing triplet.
4. Array with Large Numbers:
   • The algorithm works with large numbers as it only performs comparisons, and the initial values are set to float('inf').

Here are a few test cases to illustrate these edge cases:

print(increasingTriplet([]))  # False
print(increasingTriplet([1, 1, 1]))  # False
print(increasingTriplet([5, 4, 3, 2, 1]))  # False
print(increasingTriplet([10**9, 10**9 + 1, 10**9 + 2]))  # True