Increasing Triplet Subsequence solution and explanation
Google
9 more videos on this problem
Increasing Triplet Subsequence | Live Coding with Explanation | Leetcode #334Algorithms Made Easy · 4:54 · 29K views
Increasing Triplet Subsequence | leetcode 334 | followup On Time O1 SpaceNaresh Gupta · 8:27 · 23K views
Increasing Triplet Subsequence | Leetcode #334Techdose · 18:57 · 20K views
Increasing Triplet Subsequence - LeetCode 334 - Python [O(n) time and O(1) space]Deepti Talesra · 10:08 · 16K views
Increasing Triplet Subsequence -(Amazon, Walmart, Facebook): Explanation ➕ Live Coding 🧑🏻💻codestorywithMIK · 24:32 · 15K views
Increasing Triplet Subsequence || Leetcode C++ || O(N) time complexity || O(1) Space complexityCode with Alisha · 5:51 · 12K views
LeetCode 334. Increasing Triplet SubsequenceHappy Coding · 11:10 · 7K views
Daily Leetcode #924: Oct 11, 2022 - 334. Increasing Triplet SubsequenceProgramming Live with Larry · 6:20 · 4K views
Increasing Triplet Subsequence || Leetcode JAVA || O(N)Udyan is here · 12:33 · 1K views
LeetCode 334 | Increasing Triplet Subsequence | Python Solution #pythonAI Learning Corner · 7:48 · 1K views
The 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
O(n) time complexity and O(1) space complexity?Approach overview
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 1: Greedy Approach using Two Variables
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.
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
first, second = float('inf'), float('inf')
for num in nums:
if num <= first:
first = num
elif num <= second:
second = num
else:
return True
return Falseclass Solution {
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= first) {
first = num;
} else if (num <= second) {
second = num;
} else {
return true;
}
}
return false;
}
}var increasingTriplet = function(nums) {
let first = Number.MAX_SAFE_INTEGER, second = Number.MAX_SAFE_INTEGER;
for (let num of nums) {
if (num <= first) {
first = num;
} else if (num <= second) {
second = num;
} else {
return true;
}
}
return false;
};#include <stdbool.h>
#include <limits.h>
bool increasingTriplet(int* nums, int numsSize) {
int first = INT_MAX, second = INT_MAX;
for (int i = 0; i < numsSize; i++) {
if (nums[i] <= first) {
first = nums[i];
} else if (nums[i] <= second) {
second = nums[i];
} else {
return true;
}
}
return false;
}public class Solution {
public bool IncreasingTriplet(int[] nums) {
int first = int.MaxValue, second = int.MaxValue;
foreach (int num in nums) {
if (num <= first) {
first = num;
} else if (num <= second) {
second = num;
} else {
return true;
}
}
return false;
}
}The Python solution uses simple comparison logic to update first and second. Upon finding a number larger than both, it returns True.
Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(1), due to constant space usage.
Approach 2: Using an Array for DP-like Solution
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.
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
if len(nums) < 3:
return False
leftMin = [float('inf')] * len(nums)
rightMax = [float('-inf')] * len(nums)
leftMin[0] = nums[0]
for i in range(1, len(nums)):
leftMin[i] = min(leftMin[i - 1], nums[i])
rightMax[-1] = nums[-1]
for i in range(len(nums) - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], nums[i])
for i in range(1, len(nums) - 1):
if leftMin[i - 1] < nums[i] < rightMax[i + 1]:
return True
return Falseclass Solution {
public boolean increasingTriplet(int[] nums) {
int n = nums.length;
if (n < 3) return false;
int[] leftMin = new int[n];
int[] rightMax = new int[n];
leftMin[0] = nums[0];
for (int i = 1; i < n; i++) {
leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
}
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 i = 1; i < n - 1; i++) {
if (leftMin[i-1] < nums[i] && nums[i] < rightMax[i+1]) {
return true;
}
}
return false;
}
}#include <stdbool.h>
#include <limits.h>
bool increasingTriplet(int* nums, int numsSize) {
if (numsSize < 3) return false;
int* leftMin = (int*)malloc(numsSize * sizeof(int));
int* rightMax = (int*)malloc(numsSize * sizeof(int));
leftMin[0] = nums[0];
for (int i = 1; i < numsSize; i++) {
leftMin[i] = leftMin[i-1] < nums[i] ? leftMin[i-1] : nums[i];
}
rightMax[numsSize - 1] = nums[numsSize - 1];
for (int i = numsSize - 2; i >= 0; i--) {
rightMax[i] = rightMax[i+1] > nums[i] ? rightMax[i+1] : nums[i];
}
for (int i = 1; i < numsSize - 1; i++) {
if (leftMin[i-1] < nums[i] && nums[i] < rightMax[i+1]) {
free(leftMin);
free(rightMax);
return true;
}
}
free(leftMin);
free(rightMax);
return false;
}In this Python solution, leftMin and rightMax arrays help identify a valid triplet condition for each middle element.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Default Approach
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;
}
};function increasingTriplet(nums: number[]): boolean {
let n = nums.length;
if (n < 3) return false;
let min = nums[0],
mid = Number.MAX_SAFE_INTEGER;
for (let num of nums) {
if (num <= min) {
min = num;
} else if (num <= mid) {
mid = num;
} else if (num > mid) {
return true;
}
}
return false;
}func increasingTriplet(nums []int) bool {
min, mid := math.MaxInt32, math.MaxInt32
for _, num := range nums {
if num > mid {
return true
}
if num <= min {
min = num
} else {
mid = num
}
}
return false
}impl Solution {
pub fn increasing_triplet(nums: Vec<i32>) -> bool {
let n = nums.len();
if n < 3 {
return false;
}
let mut min = i32::MAX;
let mut mid = i32::MAX;
for num in nums.into_iter() {
if num <= min {
min = num;
} else if num <= mid {
mid = num;
} else {
return true;
}
}
false
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach using Two Variables | Time Complexity: O(n), where n is the number of elements. |
| Using an Array for DP-like Solution | Time Complexity: O(n). |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Increasing Triplet Subsequence easy or hard?
Increasing Triplet Subsequence is classified as a Medium difficulty problem. The brute-force or DP-style reasoning is straightforward, but recognizing the greedy optimization that reduces the problem to two tracked values requires deeper algorithmic insight.
Increasing Triplet Subsequence Python/Java solution
Python and Java implementations typically follow the greedy two-variable pattern. Initialize two variables to large values, iterate through the array, update the first or second candidate accordingly, and return true when a third larger value appears. The implementation is short and runs in O(n) time.
How to solve Increasing Triplet Subsequence in O(n)?
Maintain two variables: the smallest value (first) and the second smallest value (second). Traverse the array and update first if the current number is smaller, update second if it fits between first and second, and return true if a number exceeds both. This single-pass greedy strategy detects a valid triplet in linear time.
What is the best approach for Increasing Triplet Subsequence?
The optimal approach is a greedy algorithm that tracks two variables representing the smallest and second-smallest values seen so far. While iterating through the array, update these values and return true when a number larger than both appears. This solution runs in O(n) time and O(1) space, making it the most efficient method.
Is Increasing Triplet Subsequence asked at Google/Amazon/Meta?
Increasing Triplet Subsequence frequently appears in interviews at large tech companies including Google, Amazon, and Meta. The question tests understanding of greedy reasoning, subsequences, and the ability to optimize from a quadratic LIS-style approach to a linear-time solution.
What data structure is used in Increasing Triplet Subsequence?
The optimal solution does not require complex data structures. It relies on simple variable tracking during a linear scan of the array. Alternative approaches may use a dynamic programming array to track subsequence lengths.
What is the time complexity of Increasing Triplet Subsequence?
The optimal greedy solution runs in O(n) time because the array is scanned once. It uses constant extra memory, so the space complexity is O(1). A simpler dynamic programming approach based on longest increasing subsequence takes O(n²) time and O(n) space.