Watch 10 video solutions for Increasing Triplet Subsequence, a medium level problem involving Array, Greedy. This walkthrough by NeetCode has 432,482 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?Problem Overview: You receive an integer array nums. The task is to determine whether there exist three indices i < j < k such that nums[i] < nums[j] < nums[k]. The elements do not need to be consecutive, only ordered by index. The goal is to detect the existence of such a triplet efficiently.
Approach 1: DP-like Subsequence Tracking with Array (O(n²) time, O(n) space)
This method treats the problem as a variation of the Longest Increasing Subsequence. Create a dp array where dp[i] stores the length of the longest increasing subsequence ending at index i. Iterate through the array, and for each index i, scan all previous indices j < i. If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1). The moment any value in dp reaches 3, an increasing triplet exists and you can return true.
This approach is straightforward and closely mirrors classic LIS logic. It explicitly tracks subsequence length and is easy to reason about during interviews when explaining subsequence problems. The tradeoff is performance: nested iteration leads to O(n²) time, which becomes slow for large inputs.
Approach 2: Greedy Using Two Variables (O(n) time, O(1) space)
The optimal solution uses a greedy observation: you only need to track the smallest possible first and second values of a potential triplet. Maintain two variables: first and second. Initialize both to a large value. Iterate through the array once. If the current number is smaller than or equal to first, update first. If it is greater than first but smaller than or equal to second, update second. If a number is greater than both, you found first < second < current, which confirms an increasing triplet.
The key insight: always keep the smallest possible candidates for the first two positions so a third larger value can complete the sequence. Each element is processed once, producing O(n) time with only constant extra memory. This pattern is a classic greedy optimization applied to an array traversal.
Recommended for interviews: The greedy two-variable approach is what most interviewers expect. It demonstrates that you recognize the subsequence constraint and can reduce the problem to maintaining minimal candidates during a single pass. Mentioning the DP/LIS-style approach first shows you understand the brute-force progression, but implementing the O(n) greedy solution shows strong algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DP-like LIS Tracking with Array | O(n²) | O(n) | When explaining the problem from a subsequence/LIS perspective or when building intuition before optimizing |
| Greedy Using Two Variables | O(n) | O(1) | Best general solution for interviews and production due to linear time and constant memory |