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 * 10^5-2^31 <= nums[i] <= 2^31 - 1
Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?
The description was taken from https://leetcode.com/problems/increasing-triplet-subsequence/.
#O(N) Time, O(1) Space
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
if len(nums) < 3:
return False
first, second = 2**32, 2**32 for num in nums:
if num <= first:
first = num
elif num <= second:
second = num
else:
return True
return FalseOne thing that may be overlooked from the problem description and isn't shown in the examples is the triplet doesn't need to contain consecutive indices.
If we had an array like this: [3,2,5,4,6], this would be perfectly valid.
That means if we wanted to implement a monotonic queue or stack, it wouldn't work.
To solve this, we can keep two number variables as we traverse the array. We could also have a three-indexed array that we would continuously shift, but that would be more complicated for the same runtime.
The goal is to find a number that is greater than the first two numbers. To achieve this, we can compare the current number with the first variable. If it is less than or equal to it, we will update the first variable to the current number. If it is not, then we will compare the current number to the second variable, seeing if it is less than equal to it. Similarly, if so, we will update the second variable to it. And at that point, we will have a second number that is greater than the first number, giving us a pair.
If it is neither less than or equal to the first two numbers, then it is greater than both numbers, giving us a triplet.
Let's start by seeing if the length of the array is less than three, if so then there couldn't possibly be a triplet that satisfies the given requirement.
If that's the case, we will return false.
if len(nums) < 3:
return False
If not, we will set our first and second numbers to a high value outside the bounds of our constraints so that they will be overwritten by the first smaller numbers within our traversal.
first, second = 2**32, 2**32
Next, we will traverse the array.
for num in nums:
If the current number is less than equal to the first number, then we will update our first number to it.
It's very important here that we use if, if-else, and else statements here because if a number is smaller than the first number, it is also smaller than the second number and we don't want to update the first and second number to the same value.
This also ensures that the indices of the values we are setting are increasing because in order to set the second number, the first number needs to be set in a previous iteration, and in order to set the third number the second number needs to be set in a previous iteration.
if num <= first:
first = num
If the current number is greater than the first number but smaller than the second number, then we will update our second number to it.
elif num <= second:
second = num
Otherwise, the current number is greater than the first two numbers so we will return true because we have found a valid triplet.
else:
return True
If we never returned true then we didn't find all three of the numbers that we needed for the triplet so we will return false.
return False