In this guide, you will get 334. Increasing Triplet Subsequence LeetCode Solution with the best time and space complexity. The solution to Increasing Triplet Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Increasing Triplet Subsequence
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.
Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
334. Increasing Triplet Subsequence LeetCode Solution in C++
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int first = INT_MAX;
int second = INT_MAX;
for (const int num : nums)
if (num <= first)
first = num;
else if (num <= second) // first < num <= second
second = num;
else
return true; // first < second < num (third)
return false;
}
}; /* code provided by PROGIEZ */
334. Increasing Triplet Subsequence LeetCode Solution in Java
class Solution {
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (final int num : nums)
if (num <= first)
first = num;
else if (num <= second) // first < num <= second
second = num;
else // first < second < num (third)
return true;
return false;
}
} // code provided by PROGIEZ
334. Increasing Triplet Subsequence LeetCode Solution in Python
class Solution:
def increasingTriplet(self, nums: list[int]) -> bool:
first = math.inf
second = math.inf
for num in nums:
if num <= first:
first = num
elif num <= second: # first < num <= second
second = num
else:
return True # first < second < num (third)
return False # code by PROGIEZ
