# Increasing Triplet Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/increasing-triplet-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/increasing-triplet-subsequence
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Nutanix](https://scaleengineer.com/companies/nutanix), [Coupang](https://scaleengineer.com/companies/coupang), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [FactSet](https://scaleengineer.com/companies/factset)
---
## Problem
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`

**Follow up:** Could you implement a solution that runs in `O(n)` time complexity and `O(1)` space complexity?

# Approaches
## Brute Force (Triple Nested Loops)
The most straightforward approach is to check every possible triplet of indices (i, j, k) where i < j < k and see if the corresponding elements form an increasing subsequence.
**Time:** O(n^3) - Three nested loops iterate through the array, where n is the number of elements in `nums`. This makes it very slow for large inputs. · **Space:** O(1) - We only use a few variables to store loop indices, so the space used is constant.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
This method iterates through all possible combinations of three distinct indices `i`, `j`, and `k` from the input array `nums`. For each combination, it ensures that the indices are in increasing order (`i < j < k`) and then checks if the corresponding values also form a strictly increasing sequence (`nums[i] < nums[j] < nums[k]`). If such a triplet is found, the function immediately returns `true`. If the loops complete without finding any such triplet, it means none exists, and the function returns `false`. This approach is easy to conceptualize but is computationally expensive due to its cubic time complexity.

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[j] && nums[j] < nums[k]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- If `n < 3`, return `false` as a triplet cannot be formed.
- Use a loop for the first element's index `i` from `0` to `n-3`.
- Inside this, use a nested loop for the second element's index `j` from `i+1` to `n-2`.
- Inside this, use another nested loop for the third element's index `k` from `j+1` to `n-1`.
- In the innermost loop, check if `nums[i] < nums[j]` and `nums[j] < nums[k]`.
- If the condition is true, we have found an increasing triplet. Return `true`.
- If the loops finish without returning, no such triplet exists. Return `false`.

## Using Auxiliary Arrays
A more optimized approach involves pre-calculating, for each element, the smallest element to its left and the largest element to its right. This allows us to check for the triplet condition in a single pass after the pre-calculation.
**Time:** O(n) - The solution involves three separate passes over the array (one for `leftMin`, one for `rightMax`, and one for the final check), each taking O(n) time. This results in a total time complexity of O(n). · **Space:** O(n) - We use two additional arrays, `leftMin` and `rightMax`, each of size `n`.
**Pros:** Significantly faster than the brute-force approach with linear time complexity.; Relatively easy to reason about.
**Cons:** Requires O(n) extra space for the auxiliary arrays, which might not be acceptable for memory-constrained environments.; Does not meet the follow-up requirement of O(1) space complexity.
### Explanation
This approach improves upon the brute-force method by reducing the time complexity from O(n^3) to O(n). The core idea is to precompute information that helps us quickly determine if an element can be the middle element of an increasing triplet. We iterate through the array and for each element `nums[j]`, we need to know if there is a smaller element to its left and a larger element to its right.
To achieve this, we use two auxiliary arrays:
1.  `leftMin`: `leftMin[i]` stores the minimum value in the subarray `nums[0...i]`.
2.  `rightMax`: `rightMax[i]` stores the maximum value in the subarray `nums[i...n-1]`.
After populating these two arrays in O(n) time, we can make a final pass through the `nums` array. For each index `j` (from 1 to n-2), we check if `leftMin[j-1] < nums[j] < rightMax[j+1]`. If this condition holds true for any `j`, we have found our increasing triplet and can return `true`.

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }

        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }

        for (int j = 1; j < n - 1; j++) {
            if (leftMin[j - 1] < nums[j] && nums[j] < rightMax[j + 1]) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Get the length of the array, `n`. If `n < 3`, return `false`.
- Create an integer array `leftMin` of size `n`. Populate it such that `leftMin[i]` stores the minimum value in `nums[0...i]`.
- Create an integer array `rightMax` of size `n`. Populate it such that `rightMax[i]` stores the maximum value in `nums[i...n-1]`.
- Iterate through the array with index `j` from `1` to `n-2`.
- For each `j`, check if `leftMin[j-1] < nums[j] < rightMax[j+1]`.
- If the condition is true, it means we've found an element `nums[j]` which has a smaller element to its left and a larger element to its right. Return `true`.
- If the loop completes, no such triplet exists. Return `false`.

## Greedy Approach
The most optimal solution uses a greedy approach. We iterate through the array while maintaining two variables, `first` and `second`, representing the smallest and second-smallest numbers of a potential increasing subsequence found so far. This allows us to find a triplet in a single pass with constant extra space.
**Time:** O(n) - We iterate through the input array `nums` only once. · **Space:** O(1) - Only two extra variables (`first` and `second`) are used, regardless of the input size.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Elegant and concise solution.
**Cons:** The logic can be slightly non-intuitive at first glance, especially how updating `first` and `second` maintains the invariant needed to find a valid triplet.
### Explanation
This is the most efficient solution, achieving linear time and constant space complexity. The idea is to iterate through the array and maintain two variables, `first` and `second`, which represent the smallest and second-smallest numbers of a potential increasing subsequence.
We initialize both `first` and `second` to the maximum possible integer value. As we traverse the array:
- If the current number `num` is less than or equal to `first`, we update `first` to `num`. This is because a smaller `first` value increases the chances of finding a `second` and `third` number to complete the triplet.
- If `num` is greater than `first` but less than or equal to `second`, we update `second` to `num`. This gives us a smaller `second` value, which makes it easier to find a third number greater than it.
- If `num` is greater than `second`, it means we have successfully found a number that is greater than both `first` and `second`. Since the way we update `first` and `second` ensures that a value for `first` was seen before a value for `second`, we have found a valid increasing triplet (`first < second < num`). We can immediately return `true`.
If we finish iterating through the entire array without this third condition ever being met, no such triplet exists, and we return `false`.

```java
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        
        for (int n : nums) {
            if (n <= first) {
                first = n; // Found a new smallest number
            } else if (n <= second) {
                second = n; // Found a new second-smallest number
            } else {
                // n > second > first, we found the triplet.
                return true;
            }
        }
        
        return false;
    }
}
```
### Algorithm
- Initialize two variables, `first` and `second`, to `Integer.MAX_VALUE`.
- Iterate through each number `num` in the `nums` array.
- If `num <= first`: update `first = num`.
- Else if `num <= second`: update `second = num`.
- Else (if `num > second`): we have found a triplet (`first`, `second`, `num`). Return `true`.
- If the loop completes, it means no increasing triplet was found. Return `false`.

# Solutions
### Java

```java
class Solution { public boolean increasingTriplet ( int [] nums ) { int min = Integer . MAX_VALUE , mid = Integer . MAX_VALUE ; for ( int num : nums ) { if ( num > mid ) { return true ; } if ( num <= min ) { min = num ; } else { mid = num ; } } return false ; } }
```

### CPP

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

### Python

```python
class Solution ( object ): def increasingTriplet ( self , nums ): """ :type nums: List[int] :rtype: bool """ a = b = float ( "inf" ) for num in nums : if num <= a : a = num elif num <= b : b = num else : return True return False ################ class Solution : # dp def increasingTriplet ( self , nums : List [ int ]) -> bool : if not nums or len ( nums ) < 3 : return False forward = [ nums [ 0 ]] for num in nums [ 1 :]: forward . append ( min ( forward [ - 1 ], num )) backward = [ nums [ - 1 ]] for num in nums [ - 2 :: - 1 ]: # costly op for insert() for runnig time backward . insert ( 0 , max ( backward [ 0 ], num )) return any ( forward [ i ] < nums [ i ] < backward [ i ] for i in range ( len ( nums ))) ############ class Solution : def increasingTriplet ( self , nums : List [ int ]) -> bool : mi , mid = inf , inf for num in nums : if num > mid : return True if num <= mi : mi = num else : mid = num return False
```