Increasing Triplet Subsequence
Increasing Triplet Subsequence is LeetCode 334 (Medium). Given an integer array nums, return true if there are indices i < j < k with nums[i] < nums[j] < nums[k], and false otherwise.
- The three values do not have to be next to each other, only in that order.
- The increase must be strict: equal values do not count.
The follow-up asks for O(n) time and O(1) extra space, with arrays of up to 5 × 10⁵ numbers.
- 1 <= nums.length <= 5 * 10⁵
- -2³¹ <= nums[i] <= 2³¹ - 1
Intuition
One scan is enough if it keeps two numbers:
first: the smallest value seen so far.second: the smallest value seen so far that has a smaller value somewhere before it. It is the end of the best pair found.
Any later number bigger than second finishes a triplet, because second already has a smaller number in front of it.
Keeping both as small as possible is the greedy part: a smaller second is easier for a future number to beat.
The question asks only whether a pattern exists, not where it is or how long it can get. That is the hint that a couple of running values can replace a full search or a DP table.
Approach
Before reading on, decide what a single running minimum cannot tell you, and what second value would close that gap. Then check your idea on [2, 1, 5, 0, 6]. Aim for O(n) time and O(1) space.
Start both values at infinity
Set first and second to infinity, meaning no value and no pair yet. The first number is then always smaller than first, and the first number after it that is bigger becomes second.
Lower first when a number is at most first
If num <= first, store it in first. A smaller start makes every future pair easier to form. An equal value also goes here, because it cannot be the larger half of a pair.
Lower second when a number fits between them
Otherwise, if num <= second, store it in second. The number is bigger than some earlier first, so it ends a real increasing pair, and it is now the cheapest such end.
Return true when a number beats second
If num is bigger than second, return true at once: the pair behind second plus num is an increasing triplet. If the scan reaches the end without this happening, return false.
Why a later first does not break the answer
In [2, 1, 5, 0, 6], first becomes 0 after second is 5. second still means "5 has the 1 before it", so 6 finishes 1, 5, 6. first only matters for the next pair: had a 3 come next, 0 and 3 would have formed a cheaper second.
Increasing Triplet Subsequence solution in Python | C++ | Java
Common pitfalls
Strict < when lowering the values
if num < first:
first = num
elif num < second:
second = numif num <= first:
first = num
elif num <= second:
second = numFor [1, 1, 2] the second 1 is not below first, so it becomes second, and 2 then beats it: the code returns true. But 1, 1, 2 is not strictly increasing, and the answer is false.
Starting both values at nums[0]
first = second = nums[0]
first = second = float("inf")For [1, 2], the 1 lowers first, and the 2 is already bigger than second, which is still 1. The code returns true with only two numbers. Starting at infinity means second holds no value until a real pair exists.
Reporting first, second, num as the triplet
return [first, second, num]
keep the first that was current when second was set
For [2, 1, 5, 0, 6] the scan ends with first = 0, second = 5, num = 6, but 0 comes after 5, so 0, 5, 6 is not in order. The real triplet is 1, 5, 6. If you must print it, save the value of first each time second changes.
Edge cases
In C++ and Java the start value is INT_MAX. A number equal to it is <= second, so it can never be counted as bigger than an empty second. [1, 2147483647, 2147483647] correctly returns false.
Complexity
Increasing Triplet Subsequence FAQ
How is this related to longest increasing subsequence?
This is the length-3 case of it. The patience-sorting LIS method keeps, for each length, the smallest value that ends an increasing run of that length. Here only lengths 1 and 2 are needed, so that list shrinks to first and second, and reaching length 3 means true.
Can I use prefix minimums and suffix maximums instead?
Yes. A number is a valid middle if the smallest value before it is smaller and the largest value after it is bigger. Two extra arrays find this in O(n) time, but they use O(n) space, so they miss the follow-up.