231. Increasing Triplet Subsequence
Medium
Greedy Thresholds
Array
Problem
Given an integer array nums, return true if there exist indices i < j < k such that nums[i] < nums[j] < nums[k]. Otherwise return false.
Examples
Example 1
Input: [1,2,3,4,5]
Output: true
Example 2
Input: [5,4,3,2,1]
Output: false
Example 3
Input: [2,1,5,0,4,6]
Output: true
Constraints
� 1 <= nums.length <= 500000
� -2147483648 <= nums[i] <= 2147483647
Hints
?? Track the smallest value seen so far.
?? Track the smallest possible second value greater than the first.
?? Any later value larger than both proves that a triplet exists.
Expected Complexity
Time: O(n)
Space: O(1)
Follow-up
Can you solve it in O(n) time and O(1) extra space?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,2,3,4,5]Expected
true