LeetCode //C - 334. Increasing Triplet Subsequence

334. Increasing Triplet Subsequence

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.

Constraints:

• $1<=nums.length<=5?10^5$
• $?2^{31}<=nums[i]<=2^{31}?1$

From: LeetCode
Link: 334. Increasing Triplet Subsequence

Solution:

Ideas：

To do this efficiently, we can use a two-pointer approach. We initialize two variables, say first and second, with the maximum possible integer values. As we iterate through the array, we update first with the smallest value found so far, and second with the smallest value greater than first. If we find an element that is greater than second, we return true as we have found our increasing triplet. If no such element is found by the end of the array, we return false.

Code:

bool increasingTriplet(int* nums, int numsSize) {
    int first = INT_MAX, second = INT_MAX;
    
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] <= first) {
            first = nums[i]; // Update first if current number is smaller than first
        } else if (nums[i] <= second) {
            second = nums[i]; // Update second if current number is greater than first but smaller than second
        } else {
            return true; // Found a number greater than both first and second
        }
    }
    
    return false; // No triplet found
}