Increasing Triplet Subsequence
Medium · Greedy · Explanation and code example
Smallest First and Second Candidates
How it works
Maintain the smallest possible first value and the smallest possible second value of an increasing pair. A new value larger than both proves that an increasing triplet exists. Replacing a candidate with a smaller value leaves more room for future values.
Steps
- Initialize both candidates to infinity.
- Replace first when the value is <= first; otherwise replace second when <= second.
- Return true if a value exceeds second.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- Use <= for updates because the subsequence must be strictly increasing.
- The values need not be adjacent.
- Lowering first does not invalidate an earlier pair represented by second.
Python code example
import math
class Solution:
def increasingTriplet(self, nums: list[int]) -> bool:
first = math.inf
second = math.inf
for num in nums:
if num <= first:
first = num
elif num <= second: # first < num <= second
second = num
else:
return True # first < second < num (third)
return False
C++ code example
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int first = INT_MAX;
int second = INT_MAX;
for (const int num : nums)
if (num <= first)
first = num;
else if (num <= second) // first < num <= second
second = num;
else
return true; // first < second < num (third)
return false;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.