334. Increasing Triplet Subsequence

Reformulated question¶

Given an integer array nums, determine whether it contains three indices i < j < k such that:

nums[i] < nums[j] < nums[k]

Return True if such a triplet exists, otherwise False.

Example:

nums = [2, 1, 5, 0, 4, 6] -> True
# choose i=1, j=4, k=5 because 1 < 4 < 6

Key trick¶

Track the smallest and second-smallest values seen so far while scanning left to right.

If you find a number bigger than both, the triplet exists.
This works in O(n) time and O(1) space.

Trap¶

Common mistakes:

Trying to find a literal increasing run of length 3 instead of any subsequence.
Using nested loops, which is too slow for 5 * 10^5 elements.
Updating the wrong “best so far” values, which breaks cases with duplicates like [1, 1, 1].
Forgetting that the middle and last values do not need to be adjacent.

Why this question is interesting¶

It tests whether you can reduce a subsequence problem to a tiny state machine.

The challenge is not brute force.
The trick is recognizing that only two thresholds matter.
It is a classic interview problem for greedy thinking and invariant maintenance.

Solution¶

class Solution:
    def increasingTriplet(self, nums: list[int]) -> bool:
        first = float("inf")
        second = float("inf")

        for x in nums:
            # x is the new smallest value
            if x <= first:
                first = x
            # x is between first and second
            elif x <= second:
                second = x
            # x is bigger than both => first < second < x
            else:
                return True

        return False

Pytest test¶

import pytest

@pytest.mark.parametrize(
    "nums, expected",
    [
        ([1, 2, 3, 4, 5], True),
        ([5, 4, 3, 2, 1], False),
        ([2, 1, 5, 0, 4, 6], True),
        ([1, 1, 1, 1], False),
        ([1, 1, 2, 2, 3], True),
        ([2, 2, 2, 2, 2], False),
        ([10, 1, 2, 3], True),
        ([2, 4, -2, -1, 0], True),
        ([5, 1, 5, 5, 2, 5, 4], True),
        ([3, 2, 1, 2, 3], True),
    ],
)
def test_increasingTriplet(nums, expected):
    assert Solution().increasingTriplet(nums) == expected

Extra¶

I was confused the first time I saw the program.

I thought that first, second and the first x value going through the last branch of the if were the triplet that leads to return True.

But this is not what the variables first and second are about. They are state variables with the following meaning:

first, when non infinit, is the global minimum so far. And when continuing scanning nums we look for values strictly superior to it.
second, when non infinit, means that there's is a couple i < j such that nums[i] < nums[j] and nums[j] = second. So in that case, while we continue scanning nums we're looking for a number strictly superior to second which will confirm the existence of such a triplet. And we can return True. In that case, we can't conclude that first is the first element of that triplet, and in fact we don't need that information: We just want to return True.

For instance:

[2, 1, 5, 0, 6] have such a triplet. increasingTriplet returns True with the following state:
```
first = 0
second = 5
x = 6
```
This following example shows that it is essential to always set first to the minimum so far, because if we didn't do that we wouldn't catch the triplet at the end of nums for the list [2, 5, 0, 1, 2]. In that case, increasingTriplet returns True with the following state:
```
first = 0
second = 1
x = 2
```