Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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
Follow up: Could you implement a solution that runs in O(n)
time complexity and O(1)
space complexity?
public boolean increasingTriplet(int[] nums) {
// start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true.
int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
for (int n : nums) {
if (n <= small) { small = n; } // update small if n is smaller than both
else if (n <= big) { big = n; } // update big only if greater than small but smaller than big
else return true; // return if you find a number bigger than both
}
return false;
}
bool increasingTriplet(vector<int>& nums) {
int c1 = INT_MAX, c2 = INT_MAX;
for (int x : nums) {
if (x <= c1) {
c1 = x; // c1 is min seen so far (it's a candidate for 1st element)
} else if (x <= c2) { // here when x > c1, i.e. x might be either c2 or c3
c2 = x; // x is better than the current c2, store it
} else { // here when we have/had c1 < c2 already and x > c2
return true; // the increasing subsequence of 3 elements exists
}
}
return false;
}
def increasingTriplet(nums):
first = second = float('inf')
for n in nums:
if n <= first:
first = n
elif n <= second:
second = n
else:
return True
return False
In our experience, we suggest you solve this Increasing Triplet Subsequence LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Increasing Triplet Subsequence LeetCode Solution
I hope this Increasing Triplet Subsequence LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>