Increasing Triplet Subsequence
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 exists, return false
.
The inituation behind the optional solution is to undstand that:
- We must traverse though the list just once.
- We keep track 2 pointers,
firstValue
andsecondValue
firstValue
is updated if we come across a valuenums[i]
such thatnums[i]<= firstValue
.secondValue
is updated only if it is larger thenfirstValue
andnums[i] <= secondValue
- If we come to a value
nums[i]
such that it is larger then bothfirstValue
andsecondValue
, we immediately return true since we have found a indexi, j, k
such thatnums[i] < nums[j] < nums[k]
firstValue
and secondValue
can be conveniently set to MAX INT to start off. This guarantees that firstValue
will be set to num[0]
to start off. As we traverse down the list, secondValue
will only be set of it is larger then firstValue
. Otherwise firstValue
will be updated.
class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums.length < 3) {
return false;
}
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int i=0; i<nums.length; i++) {
int currentValue = nums[i];
if (currentValue <= first) {
first = currentValue;
} else if (currentValue <= second) {
second = currentValue;
} else {
return true;
}
}
return false;
}
}
Conclusion
The examples that are presented along with the question are very important. It is very common for candidates to make the mistake that i, j and k must be subsequent positions one after each other (i.e. i, j = i + 1, and k = i + 2).