Increasing Triplet Subsequence

Problem Description

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 exist, return false.

Key Insights

• We need to identify a triplet in the array where the elements are strictly increasing.
• A direct approach of using three nested loops would be inefficient, especially for large arrays.
• A more efficient solution can be achieved by maintaining two variables to track the first two elements of the increasing triplet.
• The solution must operate in O(n) time complexity and O(1) space complexity.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a greedy approach with two variables to track the smallest and the second smallest elements encountered in the array. The algorithm proceeds as follows:

1. Initialize two variables, first and second, to represent the first and second elements of the increasing triplet, respectively.
2. Iterate through the array:
   • If the current element is less than or equal to first, update first.
   • If the current element is greater than first but less than or equal to second, update second.
   • If the current element is greater than second, it means we have found a valid triplet: first < second < current.
3. If such a triplet is found during the iteration, return true. If the loop completes without finding a triplet, return false.

Code Solutions