MediumNo. 0334
Increasing Triplet Subsequence — LeetCode 334 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array
- On a study list
- LeetCode 75
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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
- Input
- nums = [1,2,3,4,5]
- Output
- true
- Explanation
- Any triplet where i < j < k is valid.
Python solution
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
mi, mid = inf, inf
for num in nums:
if num > mid:
return True
if num <= mi:
mi = num
else:
mid = num
return FalseComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 334. Increasing Triplet Subsequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0330 | Patching Array | Hard |
| 0324 | Wiggle Sort II | Medium |
| 0011 | Container With Most Water | Medium |
| 0134 | Gas Station | Medium |
| 0135 | Candy | Hard |
| 0179 | Largest Number | Medium |
Frequently asked questions
- How hard is LeetCode 334. Increasing Triplet Subsequence?
LeetCode 334. Increasing Triplet Subsequence is rated Medium on LeetCode.
- What topics does LeetCode 334. Increasing Triplet Subsequence cover?
LeetCode 334. Increasing Triplet Subsequence is tagged Greedy and Array on LeetCode.