
Description
The problem requires determining if there exists a strictly increasing subsequence of length 3 in a given array of integers, nums
. A strictly increasing subsequence means that for any triplet of indices \( i < j < k \), we must have \( nums[i] < nums[j] < nums[k] \).
Intuition
To solve this problem, the key is to maintain two variables that capture the smallest and the second smallest elements encountered so far in the array. If we can find a third element greater than these two, then an increasing triplet exists. By iterating through the array and updating these two variables accordingly, we can efficiently determine if such a triplet exists.
Approach
- Initialize two variables,
prev1
andprev2
, to infinity. These will store the smallest and second smallest values found so far, respectively. - Traverse the array. For each element:
- If it is greater than
prev2
, then we have found a triplet where \( prev1 < prev2 < current\_element \), so returnTrue
. - If it is greater thanprev1
but less than or equal toprev2
, updateprev2
to be this element. - If it is less than or equal toprev1
, updateprev1
to be this element. - If the loop completes without finding such a triplet, return
False
.
Complexity
Time Complexity:
( O(n) ), where ( n ) is the length of the input array. This is because we only traverse the array once.
Space Complexity:
( O(1) ), as we are using only a constant amount of extra space for the two variables prev1
and prev2
.
Code
C++
class Solution {
public:
bool increasingTriplet(vector& nums) {
int prev1 = INT_MAX;
int prev2 = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > prev2 && prev2 > prev1) {
return true;
}
if (nums[i] > prev1) {
prev2 = nums[i];
} else {
prev1 = nums[i];
}
}
return false;
}
};
Python
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
prev1 = float('inf')
prev2 = float('inf')
for num in nums:
if num > prev2 and prev2 > prev1:
return True
if num > prev1:
prev2 = num
else:
prev1 = num
return False
Java
class Solution {
public boolean increasingTriplet(int[] nums) {
int prev1 = Integer.MAX_VALUE;
int prev2 = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > prev2 && prev2 > prev1) {
return true;
}
if (nums[i] > prev1) {
prev2 = nums[i];
} else {
prev1 = nums[i];
}
}
return false;
}
}
JavaScript
var increasingTriplet = function (nums) {
let prev1 = Infinity;
let prev2 = Infinity;
let isIncreasingTriplet = false;
for (var indexI = 0; indexI < nums.length; indexI++) {
if (nums[indexI] > prev2 && prev2 > prev1) {
isIncreasingTriplet = true;
break;
}
if (nums[indexI] > prev1) prev2 = nums[indexI];
else prev1 = nums[indexI];
}
return isIncreasingTriplet;
};