# 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:

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.Iterate through the

`nums`

array using a for...of loop, where`num`

represents the current element being considered.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.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.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.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