334.IncreasingTriplet.cs

// 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 * 105
// -231 <= nums[i] <= 231 - 1

//BruteForce: O(n^3)
public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        for(int i = 0; i < nums.Length-2; i++)
            for(int j = i+1; j < nums.Length-1; j++)
                for(int k = j+1; k < nums.Length; k++)
                    if(nums[i] < nums[j] && nums[j] < nums[k])
                        return true;
        
        return false;
    }
}

// O(n)
public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        int firstMin = int.MaxValue, secondMin = int.MaxValue;

        foreach(var num in nums){
            if(num <= firstMin)
                firstMin = num;
            else if(num <= secondMin)
                secondMin = num;
            else 
                return true;
        }
        return false;
    }
}