Increasing Triplet Subsequence

                                            
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, second = INT_MAX;
        
        for(int num : nums){
            if(num <= first){
                first = num;
            }else if(num <= second){
                second = num;
            }else{
                return true;
            }
        }
        
        return false;
    }
};

                                            
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        int small = Integer.MAX_VALUE;
        int big = Integer.MAX_VALUE;
        
        for (int num : nums) {
            if (num <= small) {
                small = num;
            } else if (num <= big) {
                big = num;
            } else {
                return true;
            }
        }
        
        return false;
    }
}

                                            
class Solution(object):
    def increasingTriplet(self, nums):
        first = second = float('inf')
        for num in nums:
            if num <= first:
                first = num
            elif num <= second:
                second = num
            else:
                return True
        return False

                                            
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];
        } else if (nums[i] <= second) {
            second = nums[i];
        } else {
            return true;
        }
    }
    
    return false;
}

                                            
public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        int small = Int32.MaxValue;
        int big = Int32.MaxValue;
        
        foreach (int num in nums) {
            if (num <= small) {
                small = num;
            }
            else if (num <= big) {
                big = num;
            }
            else {
                return true;
            }
        }
        
        return false;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {boolean}
 */
const increasingTriplet = (nums) => {
    let first = Infinity;
    let second = Infinity;

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

    return false;
};

                                            
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;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function increasingTriplet($nums) {
        $first = PHP_INT_MAX;
        $second = PHP_INT_MAX;
        
        foreach ($nums as $num) {
            if ($num <= $first) {
                $first = $num;
            } elseif ($num <= $second) {
                $second = $num;
            } else {
                return true;
            }
        }
        
        return false;
    }
}

                                            
class Solution {
    func increasingTriplet(_ nums: [Int]) -> Bool {
        var small = Int.max
        var big = Int.max
        
        for num in nums {
            if num <= small {
                small = num
            } else if num <= big {
                big = num
            } else {
                return true
            }
        }
        
        return false
    }
}

                                            
class Solution {
    fun increasingTriplet(nums: IntArray): Boolean {
        var small = Int.MAX_VALUE
        var big = Int.MAX_VALUE
        
        for (num in nums) {
            if (num <= small) {
                small = num
            } else if (num <= big) {
                big = num
            } else {
                return true
            }
        }
        
        return false
    }
}

                                            
class Solution {
  bool increasingTriplet(List<int> nums) {
    int first = 2147483647, second = 2147483647;
    for (int num in nums) {
      if (num <= first) {
        first = num;
      } else if (num <= second) {
        second = num;
      } else {
        return true;
      }
    }
    return false;
  }
}

                                            
func increasingTriplet(nums []int) bool {
    min1, min2 := math.MaxInt32, math.MaxInt32
    
    for _, num := range nums {
        if num <= min1 {
            min1 = num
        } else if num <= min2 {
            min2 = num
        } else {
            return true
        }
    }
    
    return false
}

                                            
# @param {Integer[]} nums
# @return {Boolean}
def increasing_triplet(nums)
    first = second = Float::INFINITY
    
    nums.each do |num|
        if num <= first
            first = num
        elsif num <= second
            second = num
        else
            return true
        end
    end
    
    false
end

                                            
impl Solution {
    pub fn increasing_triplet(nums: Vec<i32>) -> bool {
        let mut small = i32::MAX;
        let mut big = i32::MAX;
        
        for num in nums {
            if num <= small {
                small = num;
            } else if num <= big {
                big = num;
            } else {
                return true;
            }
        }
        
        false
    }
}

To solve this coding challenge, you need a method that efficiently checks whether there exists a triplet of indices in a given integer array that satisfies the criteria \(i < j < k\) and \(nums[i] < nums[j] < nums[k]\). The problem also specifies that the algorithm should operate in \(O(n)\) time complexity and \(O(1)\) space complexity for optimal performance.

Explanation

The solution to this problem involves traversing the array while keeping track of two variables:

first

and

second

. These variables will be used to store the smallest and the second smallest values found so far, respectively. As we iterate through the array, the following steps will be performed:

Initialization :

Initialize
first

to a very large number (
inf

) to keep track of the smallest number found thus far.
Initialize
second

to a very large number (
inf

) to keep track of the second smallest number found thus far.

Iteration and Comparison :

Iterate through each element in the array.
For each element, compare it with
first

:

If the element is smaller than or equal to
first

, update
first

to the current element's value.

If the element is larger than
first

but smaller than or equal to
second

, update
second

to the current element's value.
If the element is larger than both
first

and
second

, it means we have found a triplet satisfying the criteria, hence return
True

.

Completion :

If the loop completes without finding such a triplet, return
False

.

This approach ensures that the time complexity is \(O(n)\) because it only requires a single pass through the array. Furthermore, it also guarantees \(O(1)\) space complexity as only a few extra variables are needed.

Detailed Steps in Pseudocode

Initialize
first

to a very large value (
inf

).
Initialize
second

to a very large value (
inf

).
Loop through each element in the array:

If the current element is less than or equal to
first

, update
first

.
Else, if the current element is less than or equal to
second

, update
second

.
Else, if the current element is greater than
second

, return
True

.

If no triplet is found, return
False

.

Pseudocode

                                            
# Initialize tracking variables to very large values
first_smallest = infinity  # Represents the smallest value found
second_smallest = infinity  # Represents the second smallest value found

# Iterate through each element in the input array
for current_value in input_array:
    
    # Check if current value is smaller or equal to first_smallest
    if current_value <= first_smallest:
        # Update first_smallest to this new smaller value
        first_smallest = current_value
        
    # Check if current value is smaller or equal to second_smallest but greater than first_smallest
    elif current_value <= second_smallest:
        # Update second_smallest to this new value as it is the second smallest found
        second_smallest = current_value
        
    # If current value is greater than both first_smallest and second_smallest
    else:
        # This means we found a valid increasing triplet
        return True

# If loop completes without returning True, there is no valid triplet
return False

This pseudocode captures the essence of the logic required to solve the coding challenge, ensuring clarity and adherence to the specified constraints. By following the approach described, you can efficiently determine whether an increasing triplet subsequence exists in the given integer array.