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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool increasingTriplet(const vector<int> &nums) {
        const int n = nums.size();
        int first = nums[0], second = numeric_limits<int>::max();
        for (int i = 1; i < n; ++i) {
            if (nums[i] > second) {
                return true;
            } else if (nums[i] > first) {
                second = nums[i];
            } else {
                first = nums[i];
            }
        }

        return false;
    }
};