334. Increasing Triplet Subsequence
## description
## 334. 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:
1Input: nums = [1,2,3,4,5]
2Output: true
3Explanation: Any triplet where i < j < k is valid.Example 2:
1Input: nums = [5,4,3,2,1]
2Output: false
3Explanation: No triplet exists.Example 3:
1Input: nums = [2,1,5,0,4,6]
2Output: true
3Explanation: One of the valid triplet is (1, 4, 5), because nums[1] == 1 < 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?
## notes
### Intuition
Track the smallest and second-smallest values seen so far. If we encounter a number larger than both, we've found an increasing triplet. The key insight is that even if smallest updates after second_smallest was set, the triplet still exists.
### Implementation
Initialize smallest and second_smallest to maximum values. Iterate through the array. If the current number is ≤ smallest, update smallest. Else if it's ≤ second_smallest, update second_smallest. Otherwise, we've found a number greater than both—return True. If the loop completes, return False.
### Edge-cases
Using ≤ (not <) handles duplicate values correctly. The algorithm works even when smallest updates to a value after second_smallest was set because a valid first element still existed when second_smallest was assigned.
- –Time: O(n) — single pass through the array
- –Space: O(1) — only two variables
### Complexity
## solution
1from typing import List
2import sys
3
4class Solution:
5 def increasingTriplet(self, nums: List[int]) -> bool:
6 smallest = second_smallest = sys.maxsize
7 for num in nums:
8 if num <= smallest:
9 smallest = num
10 elif num <= second_smallest:
11 second_smallest = num
12 else:
13 return True
14 return False
15
16
17
18if __name__ == "__main__":
19 # Include one-off tests here or debugging logic that can be run by running this file
20 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
21 solution = Solution()
22