Increasing Triplet Subsequence
Medium· greedy scan
Problem
Determine whether there exist indices i < j < k with nums[i] < nums[j] < nums[k]. The three values need not be adjacent. Solve it in one pass with constant space.
Examples
Input: nums = [2,6,1,3,5]
Output: true
The values 1, 3, 5 at indices 2, 3, 4 are strictly increasing.
Input: nums = [9,7,4,3]
Output: false
Constraints
- • 1 <= nums.length <= 5 * 10^5
- • -2^31 <= nums[i] <= 2^31 - 1
Hints & approach
Hint 1
Keep track of the smallest value seen so far.
Hint 2
Also keep the smallest value that has something smaller before it.
Hint 3
If a new value beats both, you have your triplet.
Approachtry the hints first
Maintain first, the smallest value seen, and second, the smallest value that has a smaller value somewhere before it; both start at infinity. For each number x: if x <= first, set first = x; else if x <= second, set second = x; else x is larger than a valid pair, so return true. Updating first later never invalidates second, because second already had a smaller predecessor.
Time O(n) · Space O(1)