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 such that .
Key Constraints & Edge Cases:
- Length: The input size can be up to , which rules out any solution worse than linear time. A brute-force approach checking all triplets would be or even optimized two-pointer approaches might hit worst-case quadratic behavior () 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 (). 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 .
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 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:
first: The smallest value seen that could serve as the start of a sequence (). We want this to be as small as possible because it makes it easier for subsequent numbers to exceed it (becoming valid or ).second: The smallest value we’ve found so far that is greater than our currentfirst. This represents the middle element () 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 ().
Approach
We will iterate through the array once with time complexity. We maintain two variables: first and second.
- 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.
- For each number in the array:
- If it is smaller than our current
first, we found an even better starting point for a triplet. Updatefirst. 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 where ). Return True immediately. - Otherwise, if it falls between
firstandsecond(), we updatesecond. This is crucial: a smaller middle element makes the condition for finding the third element easier to satisfy later.
- If it is smaller than our current
Complexity Analysis
- Time: - We traverse the array exactly once with constant-time operations per iteration.
- Space: - We only use two integer variables (
firstandsecond) 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
secondwill 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, ifnum == first, it goes to theelsebranch updatingsecond. 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.