Domain 2MediumCORE

Increasing Triplet Subsequence

We are looking for the existence of an increasing subsequence of length 3 within a given array nums. Specifically, we need indices $i < j < k$ such that $nums[i] < nums[j] < nums[k]$.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 1

334. Increasing Triplet Subsequence

Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 40.9%


Problem Breakdown

We are looking for the existence of an increasing subsequence of length 3 within a given array nums. Specifically, we need indices i<j<ki < j < k such that nums[i]<nums[j]<nums[k]nums[i] < nums[j] < nums[k].

Key Constraints & Edge Cases:

  • Length: The input size can be up to 10510^5, which rules out any solution worse than linear time. A brute-force approach checking all triplets would be O(n3)O(n^3) or even optimized two-pointer approaches might hit worst-case quadratic behavior (O(n2)O(n^2)) if not careful with state management.
  • Values: Integers can range from negative to positive limits (standard 32-bit integer bounds). Python handles large integers automatically, so overflow isn’t a concern for the language itself, but we must respect strict inequality logic.
  • Duplicates/Equality: The condition is strictly increasing (<<), not non-decreasing (≤\le). If nums[i] == nums[j], that does not count as an increase.
  • Small Arrays: If length < 3, a triplet cannot exist by definition of indices i<j<ki<j<k.

Intuition

Let’s start with the brute force idea: iterate through every possible middle element and check if there is something smaller before it and larger after it. While correct, this requires nested loops or sorting logic that often leads to O(n2)O(n^2) time complexity due to searching for elements in subarrays.

To optimize, we need a greedy strategy. We don’t actually care about the specific triplet values; we only care if one exists. As we scan through nums, we want to maintain two “virtual pointers” representing our best candidates so far:

  1. first: The smallest value seen that could serve as the start of a sequence (ii). We want this to be as small as possible because it makes it easier for subsequent numbers to exceed it (becoming valid jj or kk).
  2. second: The smallest value we’ve found so far that is greater than our current first. This represents the middle element (jj) of a potential triplet. We also want this as small as possible, because finding something larger than it later will complete the sequence.

The Logic: If we encounter a number smaller than first, we update first to that new minimum (resetting our start). If we find a number between first and second, we update second. This effectively “resets” our middle element candidate to something easier for the future. Finally, if we see a number larger than both first and second, we have found our triplet (nums[i]<nums[j]<currentnums[i] < nums[j] < \text{current}).

Approach

We will iterate through the array once with O(n)O(n) time complexity. We maintain two variables: first and second.

  1. Initialize both to infinity (or a value larger than any possible input) so that valid numbers update them immediately. Alternatively, handle initialization implicitly by checking conditions against these sentinels.
  2. For each number in the array:
    • If it is smaller than our current first, we found an even better starting point for a triplet. Update first. This doesn’t invalidate previous progress because if a valid pair existed before, and we haven’t returned True yet, that path was dead-ended or suboptimal compared to this new start.
    • If it is larger than our current second, we have found the third element of an increasing triplet (since there must be some index i<ji < j where nums[i]≤first<second<nums[k]nums[i] \le first < second < nums[k]). Return True immediately.
    • Otherwise, if it falls between first and second (first<num≤secondfirst < num \le second), we update second. This is crucial: a smaller middle element makes the condition for finding the third element easier to satisfy later.

Complexity Analysis

  • Time: O(n)O(n) - We traverse the array exactly once with constant-time operations per iteration.
  • Space: O(1)O(1) - We only use two integer variables (first and second) regardless of input size.

Solution

import math

def increasingTriplet(nums):
    # Initialize first and second to infinity so any valid number updates them immediately.
    # Using float('inf') is safe in Python for comparison with integers, 
    # but logically represents a value larger than max constraint (2^31 - 1).
    first = math.inf
    second = math.inf
    
    for num in nums:
        if num < first:
            # Found a new smaller starting point. This is always beneficial because
            # it makes the condition 'num > first' easier to satisfy later.
            first = num
        elif num > second:
            # We found a number larger than our current best middle element (second).
            # Since we know there exists some previous value <= first < second, 
            # this completes an increasing triplet of length 3.
            return True
        else:
            # The number is greater than or equal to 'first' but not greater than 'second'.
            # It becomes a better candidate for the middle element (smaller 'second').
            second = num
            
    # If we finish iterating without returning True, no triplet exists.
    return False

# Example usage:
print(increasingTriplet([1, 2, 3, 4, 5]))      # Output: True
print(increasingTriplet([5, 4, 3, 2, 1]))     # Output: False
print(increasingTriplet([2, 1, 5, 0, 4, 6]))   # Output: True (triplet indices for values)

Edge Cases Handled

  • Length < 3: The loop runs but second will never be updated to a value that allows the final condition (num > second) unless we have at least three distinct increasing steps. If length is small, logic naturally returns False as no triplet can form.
  • Strict Inequality (Duplicates): The conditions use < and >. Specifically, if num == first, it goes to the else branch updating second. This ensures we don’t accidentally count equal values in a strictly increasing sequence unless they are distinct indices with strict value increase later.
  • Negative Numbers: Python handles negative integers correctly; comparisons work as expected (e.g., -5 < -2). The infinity sentinel is larger than any valid integer input, so initialization remains safe.