334. Increasing Triplet Subsequence

Increasing Triplet Subsequence

Problem 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 exist, 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?

Ideas:

This question is to solve whether there are three increasing permutations of sequential numbers. Note that there is no requirement to be continuous here, so ideas such as sliding windows are not possible. The title requires O(n) time complexity and O(1) space complexity, so the violent approach does not need to be considered.

Our goal is to find three numbers in increasing order. Therefore, our approach can be to traverse in turn and then maintain three variables, record the minimum value, the second minimum value, and the third minimum value respectively. Returns true as long as we can fill these three variables, otherwise returns false.

Analysis of key points

Maintain three variables, and record the minimum value, the second minimum value, and the third minimum value respectively. Returns true as long as we can fill these three variables, otherwise returns false

Code:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) {
    if (nums.length < 3) return false;
    let n1 = Number.MAX_VALUE;
    let n2 = Number.MAX_VALUE;

    for(let i = 0; i < nums.length; i++) {
        if (nums[i] <= n1) {
            n1 = nums[i]
        } else if (nums[i] <= n2) {
            n2 = nums[i]
        } else {
            return true;
        }
    }

    return false;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #334. Increasing Triplet Subsequence

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!