Increasing Triplet Subsequence

Problem

Given an integer array nums, decide whether there exist three indices i < j < k such that nums[i] < nums[j] < nums[k]. Return True if such an increasing triplet (not necessarily contiguous) exists, False otherwise.

You only need to report existence — you do not have to return the indices.

Examples

• nums = [1,2,3,4,5] → True — 1 < 2 < 3 (many triplets work).
• nums = [5,4,3,2,1] → False — strictly decreasing, so no increasing triple exists.
• nums = [2,1,5,0,4,6] → True — the triplet 1 < 4 < 6 (indices 1, 4, 5) increases.

Constraints

• 1 <= len(nums) <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

The half-million bound and the “can you do it in O(n) time and O(1) space?” follow-up steer you away from the cubic and quadratic solutions.

Think about it first

TL;DR

Track the smallest value (first) and the smallest value that has something smaller before it (second); any element beating second proves a triplet — O(n) time, O(1) space.

Approach 1 — Brute force: three nested loops

Try every ordered triple of indices.

from typing import List

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] < nums[j] < nums[k]:
                        return True
        return False

Complexity: O(n^3) time, O(1) space. At n = 5 * 10^5 this is astronomically slow.

Approach 2 — Precompute left-min and right-max (DP-style baseline)

The insight: index j is the middle of a triplet iff some element to its left is smaller and some element to its right is larger. Precompute, for each position, the minimum to the left and the maximum to the right; then one scan checks the middle condition.

from typing import List

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        left_min = [0] * n
        right_max = [0] * n
        left_min[0] = nums[0]
        for i in range(1, n):
            left_min[i] = min(left_min[i - 1], nums[i])
        right_max[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], nums[i])
        for j in range(1, n - 1):
            if left_min[j - 1] < nums[j] < right_max[j + 1]:
                return True
        return False

Complexity: O(n) time but O(n) space for the two auxiliary arrays. This is the clear, easy-to-prove version — good to know, but it fails the O(1)-space follow-up.

Approach 3 — Two running minima (the greedy)

The greedy-choice property (why the local update is globally correct): Scan left to right holding two values, first (smallest seen so far) and second (smallest value for which a strictly smaller element appeared before it). Each new number x:

• if x <= first, lower first — a smaller candidate small can only help a future triplet, and lowering first never invalidates an already-recorded second;
• else if x <= second, lower second — we now have a valid (some earlier first) < x pair, and we keep the pair’s top as small as possible so more values can beat it later;
• else x > second, and a triplet exists.

The subtle point: after we later lower first to a value positioned after the element that set second, it can look like first and second are out of order. That is fine — the guarantee we rely on is only that at the moment second was assigned, a genuinely smaller element preceded it. That historical fact never expires, so the instant any x exceeds second, a real i < j < k chain is certified. Greedily keeping both bounds as small as possible maximizes the chance a future element clears second, and it never produces a false positive.

from typing import List

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

Walkthrough on nums = [2,1,5,0,4,6]:

1. x=2: 2 <= inf → first=2. (first=2, second=inf)
2. x=1: 1 <= 2 → first=1. (first=1, second=inf)
3. x=5: 5 > 1 and 5 <= inf → second=5. (first=1, second=5)
4. x=0: 0 <= 1 → first=0. (first=0, second=5 — now “out of order,” but second=5 still remembers a smaller-before-it existed.)
5. x=4: 4 > 0 and 4 <= 5 → second=4. (first=0, second=4)
6. x=6: 6 > 0 and 6 > 4 → return True. ✅ (the certified triplet is 1 < 4 < 6.)

Complexity: O(n) time, O(1) space. Meets the follow-up.

Common pitfalls

• Using < instead of <= in the comparisons. With <, duplicate values like [1,1,1,1] or ties can be mishandled; <= correctly keeps equal values from spuriously advancing to second.
• Being spooked by first ending up positioned after the element that set second. It does not cause false positives — the proof relies only on the history at assignment time.
• Overflow worries: use float('inf') sentinels (or None checks) so the initial comparisons behave.

Pattern takeaway

To detect a length-L increasing subsequence cheaply, greedily maintain the smallest possible “tail” for each achievable length (here first and second). Keeping every bound minimal maximizes future extendability — the same idea generalizes to the patience-sorting O(n log n) longest-increasing-subsequence algorithm.