334. Increasing Triplet Subsequence
1. Description
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.
2. Example
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: One of the valid triplet is (1, 4, 5), because nums[1] == 1 < nums[4] == 4 < nums[5] == 6.
3. Constraints
- 1 <= nums.length <= 5 * $10^5$
- -$2^{31}$ <= nums[i] <= $2^{31}$ - 1
4. Solutions
Greedy
n = nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
bool increasingTriplet(const vector<int> &nums) {
int first_num = nums[0], second_num = INT_MAX;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] > second_num) {
return true;
} else if (nums[i] > first_num) {
second_num = nums[i];
} else {
first_num = nums[i];
// Note that second_num may appear before first_num.
// This does not matter: if a value can serve as second_num,
// there must exist a smaller value that can act as first_num.
// We only care about the existence of a valid solution,
// not the exact indices or values.
}
}
return false;
}
};