Increasing Triplet Subsequence

Problem Statement

The task is to determine if there exists a triplet (i, j, k) in a given array nums such that:

• The indices satisfy the order i < j < k.
• The elements at these indices satisfy the inequality nums[i] < nums[j] < nums[k].

In other words, you are asked to find out whether there is a sequence of three strictly increasing numbers appearing in the array according to their order of indices. If such a triplet exists, the function should return true, otherwise, it should return false.

Examples

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 * 105
• -231 <= nums[i] <= 231 - 1

Approach and Intuition

To tackle this problem effectively, it is beneficial to think about how we could efficiently check for the conditions of having three increasing ordered numbers:

1. Initial Thoughts:

   • A brute-force solution could involve checking all possible combinations of triplets in the array. However, this would be highly inefficient, especially with the upper constraint of the array’s length.

2. Optimization Insight:

   • We should look out for the smallest number seen so far (small) and check if we can find a middle number (middle) greater than small but less than some numbers appearing after middle.

3. Operational Steps:

   1. Traverse through the array while keeping track of the smallest value found so far — categorize it as small.
   2. Look for another number that is larger than small yet less than another subsequent number, treating this as middle.
   3. If we can find another number greater than middle as we continue, then a triplet exists.

4. Runtime Consideration:

   • By tracking the needed values during a single pass in the array, or utilizing optimized data structures like stacks, we can considerably lower the runtime from the naive approach.

5. Edge Cases:

   • Arrays with less than three numbers automatically don’t satisfy the conditions (though this is restricted by the constraints).
   • Arrays where all elements are decreasing or all are same also fail.

From the example cases provided:

• Example 1 demonstrates a clear strictly increasing series.
• Example 2 illustrates a decreasing sequence, showing why it’s impossible to find a valid triplet.
• Example 3 highlights that the triplet need not be contiguous, merely increasing with correct index ordering.

Solutions

class Solution {
    public boolean hasTripletSequence(int[] sequence) {
        int low = Integer.MAX_VALUE;
        int mid = Integer.MAX_VALUE;
        for (int val: sequence) {
            if (val <= low) {
                low = val;
            } else if (val <= mid) {
                mid = val;
            } else {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def hasTripletSubsequence(self, sequence: List[int]) -> bool:
        low = float("inf")
        mid = float("inf")
        for value in sequence:
            if value <= low:
                low = value
            elif value <= mid:
                mid = value
            else:
                return True
        return False