334. Increasing Triplet Subsequence - cocoder39/coco39_LC GitHub Wiki
334. Increasing Triplet Subsequence
Option 1: Most efficient solution, which maintains 2 variables indicating the smallest and 2nd smallest elements. Once the logic falls into the else block, it means we have found a triplet, namely [first, second, num].
Update [first, second, num] may not be the triplet. EG Given [2, 6, 1, 8], we would end up having [1, 6, 8] but the actual triplet should be [2, 6, 8]. So this approach can validate if there exists a triplet but it doesn't tell us correctly what the triplet is. In other words, it can not be extended to support requirement like get the triplet
Option 2: liner scan with O(n) space complexity
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
n = len(nums)
minAtLeft = [float("inf")] * n
maxAtRight = [-float("inf")] * n
for i in range(1, n):
minAtLeft[i] = min(minAtLeft[i-1], nums[i-1])
for i in range(n-2, -1, -1):
maxAtRight[i] = max(maxAtRight[i+1], nums[i+1])
for i in range(1, n-1):
if minAtLeft[i] < nums[i] < maxAtRight[i]:
return True
return False
Option 3 (best): This problem is a special case of longest increasing subsequence where we simply check if the there exists a LSI of length >= 3.
T(n) = O(1). We perform binary search against an array of length 3 S(N) = o(1). We maintain an array of length 3.
======================================================
a simple version of 300. Longest Increasing Subsequence
bool increasingTriplet(vector<int>& nums) {
int first = INT_MAX;
int second = INT_MAX;
for (auto num : nums) {
if (num <= first)
first = num;
else if (num <= second)
second = num;
else
return true;
}
return false;
}
bool increasingTriplet(vector<int>& nums) {
vector<int> triplet;
for (int i = 0; i < nums.size() && triplet.size() < 3; i++) { //O(n)
auto it = lower_bound(triplet.begin(), triplet.end(), nums[i]);
if (it == triplet.end()) {
triplet.push_back(nums[i]);
}
else {
*it = nums[i];
}
}
return triplet.size() == 3;
}