mirror of
https://github.com/devenperez/leetcode.git
synced 2026-06-15 09:57:09 +00:00
Deven
37 lines
1.5 KiB
Markdown
37 lines
1.5 KiB
Markdown
<h2><a href="https://leetcode.com/problems/increasing-triplet-subsequence">334. Increasing Triplet Subsequence</a></h2><h3>Medium</h3><hr><p>Given an integer array <code>nums</code>, return <code>true</code><em> if there exists a triple of indices </em><code>(i, j, k)</code><em> such that </em><code>i < j < k</code><em> and </em><code>nums[i] < nums[j] < nums[k]</code>. If no such indices exists, return <code>false</code>.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<pre>
|
|
<strong>Input:</strong> nums = [1,2,3,4,5]
|
|
<strong>Output:</strong> true
|
|
<strong>Explanation:</strong> Any triplet where i < j < k is valid.
|
|
</pre>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<pre>
|
|
<strong>Input:</strong> nums = [5,4,3,2,1]
|
|
<strong>Output:</strong> false
|
|
<strong>Explanation:</strong> No triplet exists.
|
|
</pre>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<pre>
|
|
<strong>Input:</strong> nums = [2,1,5,0,4,6]
|
|
<strong>Output:</strong> true
|
|
<strong>Explanation:</strong> One of the valid triplet is (1, 4, 5), because nums[1] == 1 < nums[4] == 4 < nums[5] == 6.
|
|
</pre>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= nums.length <= 5 * 10<sup>5</sup></code></li>
|
|
<li><code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code></li>
|
|
</ul>
|
|
|
|
<p> </p>
|
|
<strong>Follow up:</strong> Could you implement a solution that runs in <code>O(n)</code> time complexity and <code>O(1)</code> space complexity? |