334. Increasing Triplet Subsequence Medium

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.

Approach

Input: An integer array nums

Output: Determine if there exists an increasing subsequence of length 3 in the array.

This problem belongs to Array + Greedy Algorithm problems.

We can maintain two numbers as small as possible:

• first: the minimum value encountered so far
• second: the second minimum value encountered "under the premise of having first"

Iterate through the array x in nums:

• If x <= first, update first = x (a smaller start is better)
• Else if x <= second, update second = x (a smaller second number with fixed first is better)
• Else (x > second), it means we found first < second < x, return true
• If the iteration finishes without returning, the answer is false.

Key Points / Common Mistakes

• Use <= for comparison, because strictly increasing requires excluding equality; using <= absorbs equal values into earlier positions.
• first and second only represent "some possible optimal prefix state", we don't need to record indices.
• Once x > second appears, we can immediately return true.

Implementation

python

from typing import List

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        # Initialize two variables to store the first two minimum values of the increasing sequence
        first = second = float('inf')

        # Iterate through each element in the array
        for num in nums:
            # If current element is less than or equal to first, update first to current element
            if num <= first:
                first = num
            # Otherwise, if current element is less than or equal to second, update second
            elif num <= second:
                second = num
            # Otherwise, it means we found a third number larger than second, return True
            else:
                return True

        # If traversal finishes without finding a valid triplet subsequence, return False
        return False

javascript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) {
    // first denotes the minimum value found so far
    let first = Infinity;
    // second denotes the second minimum value found after first
    let second = Infinity;

    // Iterate through the array
    for (let num of nums) {
        if (num <= first) {
            // If num is smaller or equal to first, update first
            // (a smaller starting point is better)
            first = num;
        } else if (num <= second) {
            // If num is greater than first but less than or equal to second
            // Update second to let it be as small as possible
            second = num;
        } else {
            // Otherwise, it implies num > second > first
            // An increasing triplet is found, directly return true
            return true;
        }
    }

    // Return false if traversal ends and nothing is found
    return false;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

334. Increasing Triplet Subsequence (English)

334. 递增的三元子序列 (Chinese)