282. Increasing Triplet Subsequence
You receive an integer array nums. Return true if there exist three indices i < j < k such that nums[i] < nums[j] < nums[k] — three values, in left-to-right order, each strictly larger than the previous. Otherwise return false.
The three elements do not need to sit next to each other; only their relative order matters. Equal values never count — the increase must be strict at both steps.
Follow-up: can you do it in O(n) time with O(1) extra space?
Example 1:
Input: nums = [2, 1, 5, 0, 4, 6]
Output: true
Explanation: Indices 3, 4, 5 hold 0 < 4 < 6 — a strictly increasing triplet in order.
Example 2:
Input: nums = [5, 4, 3, 2, 1]
Output: false
Explanation: The array only ever decreases, so no pair increases — let alone a triplet.
Example 3:
Input: nums = [20, 100, 10, 12, 5, 13]
Output: true
Explanation: 10 < 12 < 13 (indices 2, 3, 5). Note the winning triplet starts well after the large 20 and 100.
Constraints:
- 1 ≤ nums.length ≤ 5 × 10⁵
- -2³¹ ≤ nums[i] ≤ 2³¹ - 1
- Follow-up target: O(n) time, O(1) extra space.
Hints:
For a fixed middle element nums[j], a triplet through j exists exactly when some element before j is smaller and some element after j is larger. Precomputing prefix minimums and suffix maximums answers that for every j in one pass each.
For O(1) space, scan once keeping two thresholds: `first` = the smallest value seen so far, and `second` = the smallest value that has something smaller before it. Any element larger than `second` completes a triplet.
Don't panic when `first` updates to a value that sits to the RIGHT of `second` — the old, valid smaller-element is still in the past, so `second` remains a truthful witness. That subtlety is the whole proof.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 1, 5, 0, 4, 6]
Expected output: true