LeetCode 334: Increasing Triplet Subsequence

Problem Restatement

We are given an integer array nums.

Return true if there exists an increasing subsequence of length 3.

That means we need indices:

i < j < k

such that:

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

The elements do not need to be consecutive. They only need to appear in increasing index order.

The problem asks for:

Input and Output

Function shape:

def increasingTriplet(nums: list[int]) -> bool:
    ...

Examples

Example 1:

Input: nums = [1,2,3,4,5]
Output: true

One valid triplet is:

1 < 2 < 3

Example 2:

Input: nums = [5,4,3,2,1]
Output: false

The sequence is strictly decreasing, so no increasing triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true

One valid triplet is:

0 < 4 < 6

First Thought: Try All Triplets

A direct approach is:

1. Choose index i.
2. Choose index j > i.
3. Choose index k > j.
4. Check whether:

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

This checks every possible triplet.

O(n^3)

This is far too slow.

We need something linear.

Key Insight

We do not need to remember all previous numbers.

We only need to track:

The goal is to eventually find a number larger than second.

If we do, then we already have:

first < second < current

which forms an increasing triplet.

The greedy idea is:

1. Keep first as small as possible.
2. Keep second as small as possible after first.

Smaller values make it easier to find a larger third value later.

Algorithm

Initialize:

first = infinity
second = infinity

Then scan the array from left to right.

For each number x:

1. If x <= first, update first.
2. Else if x <= second, update second.
3. Else:
   1. We found:

first < second < x

2. Return True.

If the loop ends without finding such a value, return False.

Walkthrough

Use:

nums = [2,1,5,0,4,6]

Start:

first = inf
second = inf

Read 2:

first = 2

Read 1:

first = 1

Smaller first value is better.

Read 5:

second = 5

Now we have an increasing pair:

1 < 5

Read 0:

first = 0

This improves the smallest value.

Read 4:

second = 4

Now we have a better increasing pair:

0 < 4

Read 6.

Since:

6 > second

we found:

0 < 4 < 6

Return True.

Why Updating first Does Not Break Things

A common confusion is:

What if second was chosen before first changed?

Example:

[2,1,5,0,4,6]

Initially:

first = 1
second = 5

Later:

first = 0

Now second = 5 came before 0.

Does that break the logic?

No.

Because later we update:

second = 4

The algorithm always maintains the best possible increasing pair seen so far.

The pair represented by (first, second) always appears in valid order inside the scanned prefix.

Correctness

The algorithm maintains these invariants while scanning the array:

When processing a value x:

If:

x <= first

then replacing first with x is always safe, because a smaller first value makes future triplets easier to form.

If:

first < x <= second

then replacing second with x is safe because we now have a smaller increasing pair:

first < x

A smaller second value increases the chance of finding a future third value larger than it.

If:

x > second

then we already have:

first < second < x

with indices in increasing order because first and second were formed during earlier iterations.

Therefore, an increasing triplet subsequence exists.

If the algorithm finishes without reaching the third case, then no increasing triplet exists in the array.

Complexity

Implementation

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

        for x in nums:
            if x <= first:
                first = x

            elif x <= second:
                second = x

            else:
                return True

        return False

Code Explanation

Initialize the two tracking values:

first = float("inf")
second = float("inf")

They represent the smallest values found so far.

For each number:

for x in nums:

If x is smaller than or equal to first, update first:

if x <= first:
    first = x

Otherwise, if x improves the second value:

elif x <= second:
    second = x

Now we have a better increasing pair.

Otherwise:

else:
    return True

This means:

x > second > first

So an increasing triplet exists.

If the loop ends, no such triplet was found.

Testing

def run_tests():
    s = Solution()

    assert s.increasingTriplet([1, 2, 3, 4, 5]) == True
    assert s.increasingTriplet([5, 4, 3, 2, 1]) == False
    assert s.increasingTriplet([2, 1, 5, 0, 4, 6]) == True

    assert s.increasingTriplet([1, 1, 1, 1]) == False
    assert s.increasingTriplet([1, 2]) == False
    assert s.increasingTriplet([1, 2, 2, 3]) == True
    assert s.increasingTriplet([20, 100, 10, 12, 5, 13]) == True

    print("all tests passed")

run_tests()

Test meaning: