Dare2Solve
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] ).
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.
prev1
and prev2
, to infinity. These will store the smallest and second smallest values found so far, respectively.prev2
, then we have found a triplet where ( prev1 < prev2 < current_element ), so return True
.prev1
but less than or equal to prev2
, update prev2
to be this element.prev1
, update prev1
to be this element.False
.( O(n) ), where ( n ) is the length of the input array. This is because we only traverse the array once.
( O(1) ), as we are using only a constant amount of extra space for the two variables prev1
and prev2
.
class Solution {
public:
bool increasingTriplet(vector<int>& 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;
}
};
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
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;
}
}
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;
};