Increasing Triplet Subsequence
The key idea
Keep the two smallest values seen so far: 'first' (smallest) and 'second' (smallest value that has a smaller value before it). The moment any later number exceeds 'second', a valid triplet first < second < current exists. Greedily lowering 'first' is safe even after 'second' is set, because 'second' still records that some smaller value once preceded it.
Problem
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exist, return false.
Constraints
- 1 <= nums.length <= 5 * 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Examples
Input: nums = [1,2,3,4,5]
Output: true
Input: nums = [5,4,3,2,1]
Output: false
Input: nums = [2,1,5,0,4,6]
Output: true
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Greedy problems
- Assign CookiesEASY
- Best Time to Buy and Sell Stock IIMEDIUM
- Boats to Save PeopleMEDIUM
- Can Place FlowersEASY
- CandyHARD
- Dota2 SenateMEDIUM
- Gas StationMEDIUM
- Hand of StraightsMEDIUM
- Jump GameMEDIUM
- Jump Game IIMEDIUM
- Lemonade ChangeEASY
- Longest Happy StringMEDIUM