Increasing Triplet Subsequence

The Problem

LeetCode 334 asks you to determine whether a given integer array contains an increasing triplet subsequence: three indices i < j < k such that nums[i] < nums[j] < nums[k]. You don't need to find the actual values, just return True if such indices exist, or False if they don't.

The brute-force O(n^3) approach checks every combination of three indices. O(n^2) is also possible by fixing j and scanning both sides. But you can do it in a single pass, O(n) time, O(1) space, and that is what makes this problem interesting.

The diagram shows nums = [2, 1, 5, 0, 4, 6]. The values 1, 4, and 6 at indices 1, 4, and 5 form a valid triplet: each index is larger than the last, and each value is larger than the last.

The Greedy Insight

You keep two sentinels:

• first -- the smallest number you have seen so far.
• second -- the smallest number you have seen that is greater than some previous first.

If you ever encounter a number that is greater than second, you have your triplet: something came before second (namely first) that was smaller, and now you have found something larger than both.

Here is the key subtlety that trips people up: when first updates to a new, lower value after second has already been set, that is fine. second still serves as proof that at some earlier point in the array there existed a number smaller than it. You don't need first to literally be to the left of second in your current state -- the history of the array guarantees it.

The Solution

def increasingTriplet(nums):
    first = second = float('inf')
    for num in nums:
        if num <= first:
            first = num
        elif num <= second:
            second = num
        else:
            return True
    return False

Walk through the logic branch by branch:

• num <= first: this is the smallest value seen yet, so update first.
• num <= second (and implicitly num > first): this number sits between first and second, so it becomes the new, tighter second.
• Otherwise: num > second > first, so you have a triplet. Return immediately.

Step-by-Step Walkthrough

Let's trace through [2, 1, 5, 0, 4, 6] one number at a time:

Notice step 4: when num = 0, first drops to 0 even though second is already 5. That can feel wrong -- surely 0 isn't to the left of 5 in the final triplet. But it doesn't matter. The fact that second = 5 was set tells us there was some earlier value smaller than 5. If anything later beats 5, a valid triplet exists. When 4 comes along in step 5 it shrinks second to 4, and then 6 finishes the job.

Complexity

A single pass through the array, two variables. That is as lean as it gets.

Building Blocks

This problem combines two ideas:

1. Greedy tracking with sentinels. Instead of remembering the whole prefix, you distil it to two numbers that capture exactly the information you need.
2. Invariant reasoning. The invariant is: if second has a finite value, then there exist at least two numbers in the prefix of the array, in increasing order, whose maximum is second. The proof is inductive over each assignment to second.

If you are comfortable with Boyer-Moore voting or the Jump Game, you have already seen this style of "carry the minimum information forward" thinking. It shows up whenever you can reformulate a search problem as a running state machine.

Edge Cases

All decreasing. In [5, 4, 3, 2, 1], every new number updates first downward. second never gets a finite value. Return False.

Length less than 3. With fewer than three elements you cannot have three distinct indices. The loop simply never hits the else branch because second stays infinite. Return False. (The problem guarantees len(nums) >= 1, so you don't need an explicit guard.)

Duplicates. The conditions use <= for both first and second, so equal values slot into first or second without triggering a false positive. A triplet requires strictly increasing values, and the else branch only fires when num > second, which is strictly greater.

Single-element runs. [1, 1, 1, 2, 2, 2]: the 1s keep refreshing first, the first 2 sets second = 2 (since 2 > first = 1 but 2 <= inf), and no number beats 2. Return False.

From Understanding to Recall

The insight here is worth committing to memory because it reappears in variants -- "increasing quadruplet", "longest increasing subsequence in O(n log n)", patience sorting. The mnemonic:

Carry two thresholds. Beat the first, become the second. Beat the second, you win.

When you revisit this problem in a week, ask yourself: what does second actually represent? Answering that question correctly in under ten seconds means the solution will flow naturally from the invariant. Spaced repetition works best when you test your understanding of why, not just what.

Related Posts

• Longest Increasing Subsequence -- the general version of this problem, solved in O(n log n) with patience sorting.
• Jump Game -- another greedy single-pass problem where you track the furthest reachable index.
• Three Sum -- a sorted two-pointer approach for finding triplets that sum to zero.