Increasing Triplet Subsequence
Medium · Arrays & Hashing · Array · Greedy
Problem
You are given an integer array nums. Return true if there exist indices i < j < k with nums[i] < nums[j] < nums[k], and false otherwise. The three values need not be next to each other, and equal values do not count as increasing.
Aim for O(n) time and O(1) extra space.
Examples
Input: nums = [6,1,5,0,4,7] Output: true
1 < 5 < 7 (indices 1, 2, 5) is one valid triplet; 0 < 4 < 7 is another.
Input: nums = [9,7,7,3] Output: false
The values never increase.
Input: nums = [3,4,1,2] Output: false
There are increasing pairs (3 < 4, 1 < 2), but no three values in increasing order.
Constraints
- 1 <= len(nums) <= 5 · 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Approaches
- Prefix minimum and suffix maximum — time O(n), space O(n)
Follow-up
For an increasing subsequence of any length k, keep k - 1 thresholds; with k unbounded and binary search over the thresholds, this becomes the O(n log n) longest increasing subsequence. The use cases ask for four in a row, and for the number of increasing triplets rather than whether one exists.
Related problems
Start free on Cariara · Coding problems · System design studio
