Increasing Triplet Subsequence

Introduction

Today, I tackled an interesting medium-level problem from LeetCode: Increasing Triplet Subsequence. This problem requires a good understanding of arrays and greedy algorithms. The goal is to determine if there exists a triplet in the array that follows the condition i<j<ki < j < ki<j<k and nums[i]<nums[j]<nums[k]nums[i] < nums[j] < nums[k]nums[i]<nums[j]<nums[k]. Let's dive into the problem statement, approach, and solution.

Problem Statement

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<ki < j < ki<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 * 10<sup>5</sup>

    • -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

Approach to Solve the Problem

To solve this problem, we can use a greedy approach. Here’s the step-by-step approach:

1. Initialize Variables: Start with two variables, first and second, and set them to the maximum possible integer value.

2. Traverse the Array: Iterate through the array while updating first and second based on the current element.

3. Update Conditions:

   • If the current element is smaller than or equal to first, update first.

   • Otherwise, if the current element is smaller than or equal to second, update second.

   • If the current element is greater than both first and second, return true as it satisfies the triplet condition.

4. Return Result: If no triplet is found, return false.

Solution

Here’s the Java code that implements the above approach:

public  static boolean find(int[] nums) {

    int first = Integer.MAX_VALUE;
    int second = Integer.MAX_VALUE;

    for(int i = 0; i < nums.length; i++){
        if(nums[i] <= first){
            first = nums[i];
        } else if (nums[i] <= second) {
            second = nums[i];
        } else{
            return true;
        }
    }

    return false;
}

Explanation

1. Initialization: first and second are initialized to Integer.MAX_VALUE to ensure that any number in the array will be smaller initially.

2. Traverse the Array: As we iterate through the array, we update first and second based on the current element's value.

3. Update Conditions: The if-else conditions ensure that first holds the smallest value encountered so far, second holds the next smallest value that is larger than first, and if we find an element larger than both, we have found our triplet.

Performance

This solution efficiently checks for the triplet in a single pass through the array, giving it a time complexity of O(n). The space complexity is O(1) as no additional space proportional to the input size is used.

Conclusion

This problem is a great example of how greedy algorithms can be used to solve array-related problems efficiently. By maintaining two variables to track the smallest and the second smallest values, we can determine the existence of the triplet in linear time.

I hope you found this explanation helpful. Stay tuned for more daily blogs on interesting problems and concepts I encounter in my learning journey!