334. Increasing Triplet Subsequence | LeetCode Solution

334. Increasing Triplet Subsequence | LeetCode Solution

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`.

Example 1:

```Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.
```

Example 2:

```Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.
```

Example 3:

```Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
```

Constraints:

• `1 <= nums.length <= 5 * 105`
• `-231 <= nums[i] <= 231 - 1`

Follow up: Could you implement a solution that runs in `O(n)` time complexity and `O(1)` space complexity?

class Solution
{
public:
bool increasingTriplet(vector<int> &nums)
{
vector<int> next(nums.size(), -1);
vector<int> prev(nums.size(), -1);
stack<int> st;
for (int i = 0; i < nums.size(); i++)
{
while (!st.empty() && nums[st.top()] < nums[i])
{
next[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();

for (int i = nums.size() - 1; i >= 0; i--)
{
while (!st.empty() && nums[st.top()] > nums[i])
{
prev[st.top()] = i;
st.pop();
}
st.push(i);
}

for (int i = 0; i < nums.size(); i++)
if (prev[i] != -1 && next[i] != -1)
return true;
return false;
}
};

class Solution
{
public:
bool increasingTriplet(vector<int> &nums)
{
int firstMin = INT_MAX;
int secondMin = INT_MAX;

for (int i : nums)
{
if (i <= firstMin)
{
firstMin = i;
}
else if (i <= secondMin)
{
secondMin = i;
}
else
return true;
}
return false;
}
};