AlgoMaster Logo

Increasing Triplet Subsequence

mediumFrequency6 min readUpdated June 23, 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 identify which three, only whether they exist.

The constraint on array size (up to 500,000) rules out O(n^2) or worse. The follow-up explicitly asks for O(n) time and O(1) space.

The central question is: as we scan through the array, what is the minimum information we need to track to know whether 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 like Integer.MAX_VALUE and Integer.MIN_VALUE without 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

Try every combination of three indices. Pick an i, then a j > i, then a k > j, and check whether the values are strictly increasing. This is a direct translation of the problem statement into code.

Algorithm

  1. For each index i from 0 to n-3:
  2. For each index j from i+1 to n-2:
  3. If nums[j] > nums[i], for each index k from j+1 to n-1:
  4. If nums[k] > nums[j], return true
  5. If no triplet found, return false

Example Walkthrough

1Initialize: check all (i, j, k) triplet combinations
0
2
1
1
2
5
3
0
4
4
5
6
1/5

Code

The three nested loops re-scan overlapping ranges from scratch for every pair. The next approach precomputes the minimum value to the left and the maximum value to the right of each position, turning each check into O(1).

Approach 2: Prefix Min and Suffix Max

Intuition

For any index j to be the middle element of a valid triplet, two conditions must hold:

  1. There is some smaller value to its left
  2. There is some larger value to its right

Which specific elements satisfy these does not matter, only that they exist.

So we precompute, for every position, the smallest value to its left and the largest value to its right. Then for each j, we check whether leftMin[j] < nums[j] < rightMax[j].

Algorithm

  1. Build a leftMin array where leftMin[i] is the minimum value in nums[0..i]
  2. Build a rightMax array where rightMax[i] is the maximum value in nums[i..n-1]
  3. For each index j from 1 to n-2, check if leftMin[j-1] < nums[j] and nums[j] < rightMax[j+1]
  4. If any such j exists, return true. Otherwise, return false.

One detail in the indexing matters: when checking position j, we compare against leftMin[j-1] and rightMax[j+1], not leftMin[j] and rightMax[j]. The left and right candidates must come from positions strictly before and after j, since the triplet needs three distinct indices i < j < k.

Example Walkthrough

1Start with nums = [2, 1, 5, 0, 4, 6]
0
2
1
1
2
5
3
0
4
4
5
6
1/5

Code

This approach achieves O(n) time but uses two auxiliary arrays of size n. The next approach tracks the same information with two variables instead of two arrays, meeting the O(1) space requirement.

Approach 3: Greedy Two Variables (Optimal)

Intuition

Instead of precomputing arrays, track two values as we scan left to right:

  • first: the smallest value seen so far (candidate for nums[i])
  • second: the smallest value seen that is greater than some earlier value (candidate for nums[j])

For any new number nums[k], if it is greater than second, we have found a triplet, because second was set based on an earlier value smaller than it.

The subtle case is when first is updated to a new, smaller value while second still holds a value that was set relative to the old first. This does not break the algorithm. Even though first now points to a different position, second still represents a valid second element: some element earlier in the array was smaller than second when second was assigned, and that element is still there. So any later value greater than second completes a valid triplet.

Algorithm

  1. Initialize first and second to infinity (or Integer.MAX_VALUE)
  2. For each number in the array:
    • If the number is less than or equal to first, update first to this number
    • Else if the number is less than or equal to second, update second to this number
    • Else, we found a number greater than both first and second, return true
  3. If the loop ends without finding a triplet, return false

Example Walkthrough

1Initialize: first = INF, second = INF
0
2
1
1
2
5
3
0
4
4
5
6
1/7

Code