Leetcode - 334. Increasing Triplet Subsequence

Medium

Jan 26, 2026

#math

#trick

334. Increasing Triplet Subsequence

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 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: One of the valid triplet is (1, 4, 5), because nums[1] == 1 < nums[4] == 4 < nums[5] == 6.

Constraints:

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Notes

Intuition

Track the smallest and second-smallest values seen so far. If we encounter a number larger than both, we've found an increasing triplet. The key insight is that even if smallest updates after second_smallest was set, the triplet still exists.

Implementation

Initialize smallest and second_smallest to maximum values. Iterate through the array. If the current number is ≤ smallest, update smallest. Else if it's ≤ second_smallest, update second_smallest. Otherwise, we've found a number greater than both—return True. If the loop completes, return False.

Edge-cases

Using ≤ (not <) handles duplicate values correctly. The algorithm works even when smallest updates to a value after second_smallest was set because a valid first element still existed when second_smallest was assigned.

Time: O(n) — single pass through the array
Space: O(1) — only two variables

Complexity

Solution

from typing import List
import sys

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        smallest = second_smallest = sys.maxsize
        for num in nums:
            if num <= smallest:
                smallest = num
            elif num <= second_smallest:
                second_smallest = num
            else:
                return True
        return False



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()