Increasing Triplet Subsequence — Problem & Solution
Increasing Triplet Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Increasing Triplet Subsequence is a medium coding problem on arrays and greedy, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Google, Microsoft, Meta, Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, return true if there exists a triple of indices i < j < k such that nums[i] < nums[j] < nums[k].
Example 1
Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any three increasing positions work.
Example 2
Input: nums = [5,4,3,2,1]
Output: false
Explanation: The array is strictly decreasing.
Example 3
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: 0 < 4 < 6 at indices 3, 4, 5.
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000
Follow-up: Can you do it in O(n) time and O(1) space?
Hints for Increasing Triplet Subsequence
Hint 1
Keep the smallest value seen so far, and the smallest value that already has something smaller before it.
Hint 2
Anything strictly greater than that second value completes a triple.
Hint 3
Lowering
firstaftersecondis set is safe —secondstill records that a valid pair existed earlier.
How to solve Increasing Triplet Subsequence
Track first, the smallest value so far, and second, the smallest value that already has something smaller before it. Any element larger than second completes a triple.
Approach
- Initialise
first = second = +∞. - For each
x: ifx <= first, setfirst = x; else ifx <= second, setsecond = x; else returntrue. - Return
false.
Why it works
second is only ever set when a smaller first preceded it, so an x > second has two smaller predecessors in order. Lowering first afterwards is safe: second still records that a valid pair existed earlier.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Using strict
<instead of<=lets equal values slip through as an "increase". - The final
firstmay sit to the right ofsecond— that does not invalidate the answer.
Reference solution
Python
def increasingTriplet(nums) -> bool:
first = second = float("inf")
for x in nums:
if x <= first:
first = x
elif x <= second:
second = x
else:
return True
return FalseJava
public static boolean increasingTriplet(int[] nums) {
long first = Long.MAX_VALUE, second = Long.MAX_VALUE;
for (int x : nums) {
if (x <= first) first = x;
else if (x <= second) second = x;
else return true;
}
return false;
}C++
bool increasingTriplet(vector<int>& nums) {
long long first = 4000000000LL, second = 4000000000LL;
for (int x : nums) {
if (x <= first) first = x;
else if (x <= second) second = x;
else return true;
}
return false;
}JavaScript
var increasingTriplet = function(nums) {
let first = Infinity, second = Infinity;
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= first) first = nums[i];
else if (nums[i] <= second) second = nums[i];
else return true;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms