Increasing Triplet Subsequence
Last Updated: March 20, 2026
Understanding the Problem
We need to find three elements in the array that are strictly increasing and appear in left-to-right order. We don't need to find which three, just whether they exist.
The constraint on array size (up to 500,000) is a strong hint that O(n^2) or worse won't cut it. The follow-up explicitly asks for O(n) time and O(1) space.
The key question to ask yourself is: as we scan through the array, what's the minimum information we need to track to know if a valid triplet can be completed?
Key Constraints:
1 <= nums.length <= 5 * 10^5→ Half a million elements means O(n^2) would be 2.5 * 10^11 operations, far too slow. We need O(n log n) or better, ideally O(n).-2^31 <= nums[i] <= 2^31 - 1→ Full 32-bit integer range. We need to handle extreme values likeInteger.MAX_VALUEandInteger.MIN_VALUEwithout overflow issues.- The follow-up asks for O(n) time and O(1) space → This pushes us toward a greedy single-pass approach rather than precomputed arrays or sorting.
Approach 1: Brute Force
Intuition
The most direct approach is to try every combination of three indices. Pick an i, then pick a j > i, then pick a k > j, and check if the values are strictly increasing.
This is what you'd naturally write if you just translated the problem statement into code.
Algorithm
- For each index
ifrom 0 to n-3: - For each index
jfrom i+1 to n-2: - If
nums[j] > nums[i], for each indexkfrom j+1 to n-1: - If
nums[k] > nums[j], return true - If no triplet found, return false
Example Walkthrough
Code
- Time Complexity: O(n^3). Three nested loops, each iterating up to n times in the worst case. For n = 500,000, this is way too slow.
- Space Complexity: O(1). Only a few index variables used.
With three nested loops, we're re-scanning overlapping ranges from scratch for every pair. What if we precomputed the minimum value to the left and maximum value to the right of each position, so each check became O(1)?
Approach 2: Prefix Min and Suffix Max
Intuition
Here's a useful observation: for any index j to be the middle element of a valid triplet, two things must be true:
- There's some smaller value to its left
- There's some larger value to its right
We don't care which specific elements those are, just that they exist.
So what if we precomputed, for every position, the smallest value to its left and the largest value to its right? Then for each j, we just check if leftMin[j] < nums[j] < rightMax[j].
Algorithm
- Build a
leftMinarray whereleftMin[i]is the minimum value innums[0..i] - Build a
rightMaxarray whererightMax[i]is the maximum value innums[i..n-1] - For each index
jfrom 1 to n-2, check ifleftMin[j-1] < nums[j]andnums[j] < rightMax[j+1] - If any such
jexists, return true. Otherwise, return false.
For any valid triplet (i, j, k), the middle element nums[j] must be strictly between the minimum of everything to its left and the maximum of everything to its right. By precomputing these two arrays, we compress all the information about the left and right sides into O(1) lookups per position.
This is a common technique for problems where you need to compare an element against some aggregate property of the elements before or after it.
Example Walkthrough
Code
- Time Complexity: O(n). Three separate passes through the array, each doing O(1) work per element. Total: 3n = O(n).
- Space Complexity: O(n). Two auxiliary arrays of size n.
This approach achieves O(n) time but uses two auxiliary arrays of size n. Can we track the same information using just two variables instead of two arrays?
Approach 3: Greedy Two Variables (Optimal)
Intuition
Here's the clever idea: instead of precomputing arrays, we track just two values as we scan left to right:
first: the smallest value we've seen so far (candidate fornums[i])second: the smallest value we've seen that is greater than some earlier value (candidate fornums[j])
For any new number nums[k], if it's greater than second, we've found our triplet, because second was set based on some earlier first value.
The tricky part that confuses people: when first gets updated to a new, smaller value, second might still hold a value that was set relative to the old first. Is that a problem?
No. Even though first now points to a different position, second still represents a valid second element of a pair. There was some element before second in the array that was smaller than second, and that relationship hasn't changed. So if anything comes along that's bigger than second, the triplet is valid.
Algorithm
- Initialize
firstandsecondto infinity (orInteger.MAX_VALUE) - For each number in the array:
- If the number is less than or equal to
first, updatefirstto this number - Else if the number is less than or equal to
second, updatesecondto this number - Else, we found a number greater than both
firstandsecond, return true - If the loop ends without finding a triplet, return false
Example Walkthrough
Code
The invariant is: at any point, second holds a value such that there exists some earlier element in the array that is strictly less than second. We don't need to remember what that earlier element was.
When first drops below second (like when we see 0 after first=1, second=5), it might seem like the invariant breaks. But second=5 was set because at the time, first was 1 (or some value less than 5). That element at index 1 is still in the array, still to the left of the position where second was set. So if we later find something bigger than 5, we have a valid triplet using that old element, the element that set second, and the new element.
This is essentially a greedy approach that generalizes to the Longest Increasing Subsequence problem. The same technique (maintaining the smallest tail values for subsequences of each length) is the foundation of the O(n log n) LIS algorithm. Here we just need length 3, so two variables suffice.
- Time Complexity: O(n). Single pass through the array, doing O(1) work per element.
- Space Complexity: O(1). Only two extra variables regardless of input size. This satisfies the follow-up requirement.