Increasing Triplet Subsequence
Increasing Triplet Subsequence: return true if there exist indices i < j < k such that nums[i] < nums[j] < nums[k].
- 1 <= nums.length <= 5 * 10⁵
- -2³¹ <= nums[i] <= 2³¹ - 1
Intuition
You do not need to know which triplet exists, only that one does. Track the smallest value seen so far and the smallest value that already has something smaller before it. Any number beating both completes a triplet — and keeping those two candidates as low as possible never loses an opportunity.
When a problem asks only whether a pattern exists — not where — you can often replace search with a couple of greedily maintained candidates. The tell is 'return true if there exist indices'. Keeping the best-so-far as small as possible is the same reasoning behind Longest Increasing Subsequence's patience-sorting variant.
Approach
Before reading on: after you lower the smallest-so-far, is the middle candidate still meaningful even though it now sits before it in value? Work out what second actually asserts. Aim for O(n) time and O(1) space.
Two running candidates are enough
Maintain first = the smallest value seen, and second = the smallest value that has some strictly smaller value before it. For each number: if it is at most first, it becomes the new first; else if it is at most second, it becomes the new second; otherwise it is greater than both, which means a valid triplet has been found. Three cases, one pass, two variables.
Why lowering the candidates is always safe
Replacing first with a smaller value cannot destroy an existing pair, because second already records that some smaller value preceded it — that historical fact stays true even though first now points elsewhere. This is the subtle part: after first is lowered, first and second may no longer be in index order, and that is fine. The only thing second asserts is there was something smaller before me, which is exactly what a third larger number needs.
Cost and the alternative
One pass, two integers: O(n) time and O(1) space, which is what the follow-up asks for. The alternative — precomputing prefix minima and suffix maxima — also runs in O(n) but needs O(n) space and two extra arrays. The greedy version is strictly better here, and the index-order subtlety is precisely what the question is testing.
Solution & live demo
Common pitfalls
Using strict < when updating the candidates
if num < first:
first = numif num <= first:
first = numWith <, an equal value falls through to the second branch and is recorded as a middle element, so [2,2,2] wrongly reports a triplet. The sequence must be strictly increasing, which means equal values must update rather than advance.
Worrying that first and second get out of order
# extra bookkeeping to keep indices aligned
first = num # simply lower it
It looks like a bug that first can end up after second in the array, but second only ever claims that something smaller came before it, and that remains true. Adding index tracking complicates the code without changing any answer.
Initialising the candidates to nums[0]
first = second = nums[0]
first = second = float('inf')Seeding with a real element makes the first comparison meaningless and breaks on arrays of length 1. Infinity guarantees the first two numbers are absorbed as candidates rather than mistaken for a match.
Edge cases
Neither candidate can be filled twice, so the function returns false.
Every value replaces first; second is never set and the answer is false.
The comparisons use <= when updating, so equal values never count as increasing.
Lowering the candidates mid-scan still finds 10 < 12 < 13.
The scan continues to the last element, so a late triplet is still detected.