334 - Increasing Triplet Subsequence

Difficulty: Medium | Pattern: Greedy | Company tags: Amazon, Facebook, Google

Problem Statement

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.

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

Example 1:

Input: nums = [1,2,3,4,5]
Output: true

Example 2:

Input: nums = [5,4,3,2,1]
Output: false

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true  (0 < 4 < 6)

Approach: Greedy Two-Tracker — O(n), O(1)

Key insight: Maintain two variables first and second — the smallest value seen so far and the smallest value greater than first seen so far. If we ever see a value greater than second, we've found our triplet.

def increasingTriplet(nums: list[int]) -> bool:
    first = second = float('inf')
    
    for n in nums:
        if n <= first:
            first = n       # update smallest
        elif n <= second:
            second = n      # update second smallest (greater than first)
        else:
            return True     # n > second > first
    
    return False

Dry Run

nums = [2,1,5,0,4,6]

n	first	second	return?
2	2	inf
1	1	inf
5	1	5
0	0	5
4	0	4
6	0	4	True

True ✓

Subtle Point: first Can Change After second is Set

When first is updated to 0 after second=5 is set, it doesn't invalidate the triplet guarantee. We have a "virtual" triplet: some value before this 0 was less than 5. The current first=0 can serve as the new starting point.

Edge Cases

• Length lt 3 → False (no triplet possible)
• All equal → False
• All increasing → True (first 3 elements form triplet)

Complexity

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