Increasing Triplet Subsequence

XXX. Increasing Triplet Subsequence

Array

Greedy

Problem Statement:

Given an integer array nums, return true if there exists a strictly increasing subsequence of length 3, and false otherwise.

• Find i < j < k where nums[i] < nums[j] < nums[k]
• Elements don't need to be adjacent
• Must maintain relative order

Implementation:

Java Solution:

public boolean increasingTriplet(int[] nums) {
    // Track smallest and second smallest values
    int min = Integer.MAX_VALUE;        // First number of triplet
    int min2 = Integer.MAX_VALUE;       // Second number of triplet
    
    for (int num : nums) {
        if (num <= min)                 // Found new smallest
            min = num;
        else if (num <= min2)           // Found new second smallest
            min2 = num;
        else                            // Found number bigger than both
            return true;
    }
    
    return false;
}
                

Python Solution:

def increasingTriplet(self, nums: List[int]) -> bool:
    # Track smallest and second smallest values
    min1 = float('inf')                # First number of triplet
    min2 = float('inf')                # Second number of triplet
    
    for num in nums:
        if num <= min1:                # Found new smallest
            min1 = num
        elif num <= min2:              # Found new second smallest
            min2 = num
        else:                          # Found number bigger than both
            return True
            
    return False
                

C++ Solution:

bool increasingTriplet(vector& nums) {
    // Track smallest and second smallest values
    int min1 = INT_MAX;                // First number of triplet
    int min2 = INT_MAX;                // Second number of triplet
    
    for (int num : nums) {
        if (num <= min1)               // Found new smallest
            min1 = num;
        else if (num <= min2)          // Found new second smallest
            min2 = num;
        else                           // Found number bigger than both
            return true;
    }
    
    return false;
}
                

Complexity:

Time Complexity: O(n), single pass through array
Space Complexity: O(1), constant extra space

Explanation:

• **Key Insight**:
  • Track two smallest values seen so far
  • Any larger value completes the triplet
  • Update values greedily for optimal result
• **Variable Meaning**:
  • min: Smallest value seen
  • min2: Smallest value greater than min
  • Current number greater than both completes sequence
• **Key Points**:
  • Values can be updated multiple times
  • Previous values remain valid for triplet
  • Order preservation is automatic