The original article is available at https://dawnmagnet.top/leetcode/2022/01/12/.

Given an integer array nums, determine whether the array contains an increasing subsequence of length 3.

Return true if there are indices (i, j, k) satisfying i < j < k and nums[i] < nums[j] < nums[k]; otherwise, return false.

Example 1:

**Input:**nums = [1,2,3,4,5]
**Output:**true
**Explanation:**Any triple of indices satisfying i < j < k meets the requirement

Example 2:

**Input:**nums = [5,4,3,2,1]
**Output:**false
**Explanation:**No triple of indices meets the requirement

Example 3:

**Input:**nums = [2,1,5,0,4,6]
**Output:**true
**Explanation:**The triple (3, 4, 5) meets the requirement because nums[3] == 0 < nums[4] == 4 < nums[5] == 6

Constraints:

• 1 &lt;= nums.length &lt;= 5 * 10<sup>5</sup>
• -2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1

Follow-up: Can you implement a solution with time complexity O(n) and space complexity O(1)?

Analysis

#

In this problem, we only need to find one triple that satisfies the conditions. A naive search over all triples would take \(O(n^3)\), which is clearly too slow. Let us first examine the conditions imposed on the triple.

A triple has two requirements: increasing indices and increasing values. The index condition is straightforward. Since the target complexity is \(O(n)\), we make one pass from left to right. During that pass, we need to record the first one or two values of a potential triple so that we can complete it when a suitable value appears.

As we scan, we keep two variables, which we call first and second. They record the first two elements that could form a triple with the current element, since we scan from left to right. Because we only get one pass, we want to make it as easy as possible to complete the triple. A smaller value gives us more opportunities, so when a smaller number appears, we replace first or second as appropriate.

This replacement depends on the current number:

• When the current number is less than first, replace first with it.
• When the current number is less than second, replace second with it.
• When the current number is greater than second, we have found an increasing triplet, so return true.

Therefore, one pass through the array is enough. If no answer is found, return false at the end.

This satisfies the follow-up requirement of \(O(n)\) time and \(O(1)\) space, because only a constant number of variables are used.

Rust Code

#

impl Solution {
    pub fn increasing_triplet(nums: Vec<i32>) -> bool {
        let mut first = nums[0];
        let mut second = i32::MAX;
        for num in &nums[1..] {
            if num > &second {
                return true;
            } else if num > &first {
                second = *num;
            } else {
                first = *num;
            }
        }
        false
    }
}