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 - 1Follow up: Could you implement a solution that runs in
O(n) time complexity and O(1) space complexity?This approach leverages two variables to track the smallest and the second smallest elements found so far in the array. As you traverse through the array, you update these two variables. If you find an element greater than the second smallest, then a triplet exists, and you return true.
This C solution iterates over the array, updating two variables, first and second, that keep track of the smallest and second smallest values. If a current element is greater than second, it confirms the existence of an increasing triplet.
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the input list, as we only traverse the list once.
Space Complexity: O(1), since we are using only a constant amount of extra space.
This approach uses an auxiliary array to keep track of the minimum elements on the left and the maximum elements on the right for each position in the array. The main idea is to check if there's any element that can serve as the middle element between some smaller and a larger element.
This solution creates two arrays, leftMin and rightMax, to store the minimum values to the left and maximum values to the right of each element. It then checks for a valid increasing triplet by ensuring there's a middle element greater than the minimum from the left and less than the maximum from the right.
Java
Python
Time Complexity: O(n), due to traversals of size n.
Space Complexity: O(n), since it uses extra space for two arrays.
| Approach | Complexity |
|---|---|
| Greedy Approach using Two Variables | Time Complexity: O(n), where n is the length of the input list, as we only traverse the list once. |
| Using an Array for DP-like Solution | Time Complexity: O(n), due to traversals of size n. |
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 432,482 views views
Watch 9 more video solutions →Practice Increasing Triplet Subsequence with our built-in code editor and test cases.
Practice on FleetCode