Increasing Triplet Subsequence
Decide whether an array has i < j < k with nums[i] < nums[j] < nums[k] in one pass, keeping only the smallest first and second values of a pair.
Problem Understanding
Increasing Triplet Subsequence (LeetCode 334): given an integer array nums, return true if there exist indices i < j < k with nums[i] < nums[j] < nums[k], and false otherwise. Aim for O(n) time and O(1) space.
Examples: [1, 2, 3, 4, 5] → true; [5, 4, 3, 2, 1] → false; [2, 1, 5, 0, 4, 6] → true (0, 4, 6).
The Intuition: Keep the Bar as Low as Possible
To finish a triplet you need a value bigger than the end of some increasing pair. The lower that pair's end, the easier it is to beat.
- first is the smallest value seen so far.
- second is the smallest value that came after something smaller.
- Any value above second completes a triplet.
Greedily keeping both as small as possible is what makes one pass enough. It is Longest Increasing Subsequence's tails idea, stopped at length 3.
Interactive Walkthrough
KEEP first AND second AS SMALL AS POSSIBLE
first = second = ∞
nums
0
1
2
3
4
5
first
∞
second
∞
Answer
:
first = second = ∞: no values seen yet
Next
2 ≤ first (∞): it is the smallest so far, so first = 2
nums
first is outlined and second tinted. Watch first jump ahead of second in Trap: the pair behind second still stands, and the real triplet turns green at the end.
Dry Run Table
Input: nums = [2, 1, 5, 0, 4, 6].
| x | Compare | first | second |
|---|---|---|---|
| 2 | ≤ ∞ | 2 | ∞ |
| 1 | ≤ 2 | 1 | ∞ |
| 5 | > 1, ≤ ∞ | 1 | 5 |
| 0 | ≤ 1 | 0 | 5 |
| 4 | > 0, ≤ 5 | 0 | 4 |
| 6 | > 4 |
6 is bigger than second. Answer: true, for example 0 < 4 < 6.
The Solution Template
Two variables and three branches. The early return is the only way to answer true.
Increasing Triplet Subsequence Code
1var increasingTriplet = function(nums) {2 let first = Infinity, second = Infinity;3 for (const x of nums) {4 if (x <= first) {5 first = x;6 } else if (x <= second) {7 second = x;8 } else {9 return true;10 }11 }12 return false;13};
Edge Cases & Common Mistakes
- Equal values: use <= so
[1, 1, 1]is false. - Fewer than 3 elements: the loop cannot reach the third branch, so false.
- Thinking first and second must be in order in the array: they need not be at the end; second's pair was recorded when it was set.
- Sentinel overflow: with INT_MAX as infinity, a value equal to INT_MAX is handled by <=, so it never counts as bigger.
Summary
Keep first as the smallest value and second as the smallest value with something smaller before it; any value larger than second proves a triplet. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet