Increasing Triplet Subsequence

Med

#0321Time: 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.5 companies

Patterns

Greedy

Data structures

Array

Companies

IBM Nutanix Coupang MakeMyTrip

Prompt

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⁵
-2³¹ <= nums[i] <= 2³¹ - 1

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean increasingTriplet(int[] nums) {3        int n = nums.length;4        if (n < 3) {5            return false;6        }7        for (int i = 0; i < n - 2; i++) {8            for (int j = i + 1; j < n - 1; j++) {9                for (int k = j + 1; k < n; k++) {10                    if (nums[i] < nums[j] && nums[j] < nums[k]) {11                        return true;12                    }13                }14            }15        }16        return false;17    }18}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

leftMin: leftMin[i] stores the minimum value in the subarray nums[0...i].
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.

1class Solution {2    public boolean increasingTriplet(int[] nums) {3        int n = nums.length;4        if (n < 3) {5            return false;6        }7 8        int[] leftMin = new int[n];9        leftMin[0] = nums[0];10        for (int i = 1; i < n; i++) {11            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);12        }13 14        int[] rightMax = new int[n];15        rightMax[n - 1] = nums[n - 1];16        for (int i = n - 2; i >= 0; i--) {17            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);18        }19 20        for (int j = 1; j < n - 1; j++) {21            if (leftMin[j - 1] < nums[j] && nums[j] < rightMax[j + 1]) {22                return true;23            }24        }25 26        return false;27    }28}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean increasingTriplet(int[] nums) {3        if (nums == null || nums.length < 3) {4            return false;5        }6        7        int first = Integer.MAX_VALUE;8        int second = Integer.MAX_VALUE;9        10        for (int n : nums) {11            if (n <= first) {12                first = n; // Found a new smallest number13            } else if (n <= second) {14                second = n; // Found a new second-smallest number15            } else {16                // n > second > first, we found the triplet.17                return true;18            }19        }20        21        return false;22    }23}

Complexity

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.

Trade-offs

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.

Solutions

Solution

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

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

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

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

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

1class 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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.