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;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.