Finding an Increasing Triplet Subsequence in an Array: A Deep Dive into the DSA Series

Introduction:

Welcome back to our Data Structures and Algorithms (DSA) series! In this installment, we'll tackle a fascinating coding challenge from LeetCode. The problem at hand is to find whether there exists an increasing triplet subsequence within an array. We'll explore the challenge, break it down step by step, and unveil a concise solution that leverages a clever algorithm.

Challenge:

The problem statement can be summarized as follows:

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.

In other words, we need to determine whether there are three distinct elements in the array that are in increasing order. The constraint here is that these elements must have strictly increasing values, meaning that nums[i] < nums[j] < nums[k], and their indices must be in ascending order as well, with i < j < k.

Solution:

To efficiently solve this problem, we can employ a simple yet clever algorithm that traverses the array while maintaining two variables, first and second. These two variables will store the lowest and second-lowest values encountered during the array traversal. The idea behind this approach is that we update these variables while iterating through the array and return true as soon as we find a value greater than or equal to second, which indicates the presence of an increasing triplet. If we complete the entire traversal without finding such a triplet, we return false.

Here is the JavaScript function that implements this algorithm:

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity;
    let second = Infinity;

    for (const num of nums) {
        if (num <= first) {
            first = num;
        } else if (num <= second) {
            second = num;
        } else {
            return true;
        }
    }
    return false;
}

Step-by-Step Explanation:

Let's break down the algorithm step by step to understand how it works:

1. Initialize two variables, first and second, both set to positive infinity (Infinity). These variables will keep track of the lowest and second-lowest values found in the array, respectively.

2. Iterate through the nums array using a for...of loop, where num represents the current element being considered.

3. Inside the loop, check if num is less than or equal to the value of first. If it is, update first with the current value of num. This ensures that first always stores the lowest value encountered so far.

4. If num is not less than or equal to first but is less than or equal to second, update second with the value of num. This ensures that second stores the second-lowest value encountered.

5. If the current element num is greater than both first and second, it means we've found a value that is larger than the previously encountered values. This is the critical moment when we've identified an increasing triplet, and we return true immediately.

6. If the loop completes without finding an increasing triplet, we return false, indicating that no such triplet exists in the array.

Conclusion:

In this article, we tackled the "Increasing Triplet Subsequence" problem from LeetCode. We walked through the problem statement, explored a step-by-step solution using JavaScript, and discussed the algorithm's key principles. This efficient algorithm allows us to determine the existence of an increasing triplet subsequence in an array with a time complexity of O(n).

I hope you found this article insightful and that it contributes to your understanding of data structures and algorithms. Stay tuned for more exciting challenges in our DSA series!
Explore Similar challenges

Let's connect