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 follow-up “can you do it in O(n) time and O(1) space?” rule out 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

def increasingTriplet(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 far too slow.

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

Index j is the middle of a triplet if and only if 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

def increasingTriplet(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 version is easy to prove correct, but it fails the O(1)-space follow-up.

Approach 3 — Two running minima (the greedy)

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). For each new number x:

• if x <= first, lower first. A smaller candidate 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 pair (some earlier first) < x, and keeping the pair’s top as small as possible lets more later values beat it.
• else x > second, so a triplet exists.

flowchart TD
  A[Next number x] --> B{x <= first?}
  B -- yes --> C[first = x]
  B -- no --> D{x <= second?}
  D -- yes --> E[second = x]
  D -- no --> F[return True]

After first is later lowered to a value positioned after the element that set second, the two can look out of order. That is fine: the only fact we rely on is that at the moment second was assigned, a smaller element preceded it. That fact never changes, so as soon as any x exceeds second, a real i < j < k chain is confirmed. Keeping both bounds minimal maximizes the chance a future element clears second, and it never produces a false positive.

from typing import List

def increasingTriplet(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 records that a smaller value preceded it.)
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 confirmed 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 <, equal values can advance to second incorrectly (for example [1,1,1,1]); <= keeps equal values from doing so.
• Assuming first positioned after the element that set second breaks the logic. It does not cause false positives, because the proof relies only on the state at assignment time.
• Initialization: use float('inf') sentinels (or None checks) so the first comparisons behave correctly.

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.