Increasing Triplet Subsequence

MediumArrays · Greedy🧩 Array Manipulation LeetCode #334 ↗Updated Oct 30, 2026

Problem

Given an integer array nums, decide whether it contains three positions i < j < k whose values are strictly increasing: nums[i] < nums[j] < nums[k]. The three positions do not have to be adjacent. Return true or false.

Inputnums = [2,1,5,0,4,6]Outputtrue (e.g. 1 < 4 < 6)

Inputnums = [5,4,3,2,1]Outputfalse

Inputnums = [1,1,1,2]Outputfalse (equal values don't count)

1 ≤ n ≤ 5·10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹-1 · Follow-up: O(n) time and O(1) space.

Try it yourself

Java

class Solution {
    public boolean increasingTriplet(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Keep the smallest possible tail of an increasing pair: the smallest value seen (first) and the smallest value that has something smaller before it (second). Any number above second completes a triplet.

PatternArray Manipulation

Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.

Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.

Open the Array Manipulation guide →

Approaches

Brute ForceCheck Every Triple

Time O(n³)Space O(1)

Three nested loops pick i < j < k and test the strict ordering. Skipping the inner loops when nums[j] ≤ nums[i] helps a little but the worst case is still cubic.

Java

public boolean increasingTriplet(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] <= nums[i]) continue;
            for (int k = j + 1; k < n; k++) {
                if (nums[k] > nums[j]) return true;
            }
        }
    }
    return false;
}

Correct and tiny, but hopeless at n = 5·10⁵.

BetterPrefix Minimum + Suffix Maximum

Time O(n)Space O(n)

Treat each index j as the middle. A triplet through it exists exactly when something smaller lies to its left and something larger lies to its right, i.e. leftMin[j] < nums[j] < rightMax[j]. Two sweeps build those arrays.

Java

public boolean increasingTriplet(int[] nums) {
    int n = nums.length;
    if (n < 3) return false;
    int[] leftMin = new int[n];  // min of nums[0..j]
    int[] rightMax = new int[n]; // max of nums[j..n-1]
    leftMin[0] = nums[0];
    for (int j = 1; j < n; j++) leftMin[j] = Math.min(leftMin[j - 1], nums[j]);
    rightMax[n - 1] = nums[n - 1];
    for (int j = n - 2; j >= 0; j--) rightMax[j] = Math.max(rightMax[j + 1], nums[j]);
    for (int j = 1; j < n - 1; j++) {
        if (leftMin[j - 1] < nums[j] && nums[j] < rightMax[j + 1]) return true;
    }
    return false;
}

Linear time and easy to prove, but uses two extra arrays.

OptimalGreedy — Two Smallest Tails

Time O(n)Space O(1)

first = smallest value so far; second = smallest value that already has a smaller one before it. Lowering either only makes a future triplet easier. When first drops below an old pair, the old second still proves a valid pair existed, so the check stays correct.

Java

public boolean increasingTriplet(int[] nums) {
    int first = Integer.MAX_VALUE;  // smallest value seen
    int second = Integer.MAX_VALUE; // smallest value with a smaller one before it
    for (int x : nums) {
        if (x <= first) {
            first = x;
        } else if (x <= second) {
            second = x;
        } else {
            return true; // first < second < x
        }
    }
    return false;
}

Dry runnums = [2,1,5,0,4,6]

x currentf firsts second changed

x=2
2
x f
1

5

0

4

6

first=2
x=1
2

1
x f
5

0

4

6

first=1
x=5
2

1
f
5
x s
0

4

6

second=5
x=0
2

1

5
s
0
x f
4

6

first=0 (pair 1,5 kept)
x=4
2

1

5

0
f
4
x s
6

second=4
x=6
2

1

5

0
f
4
s
6
x
6 > 4 → true ✔

One pass, two variables — meets the follow-up exactly.

Pro tip

Use <= in both comparisons — with <, duplicates like [1,1,1] would wrongly be accepted.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Triple	`O(n³)`	`O(1)`
Better	Prefix Minimum + Suffix Maximum	`O(n)`	`O(n)`
Optimal	Greedy — Two Smallest Tails	`O(n)`	`O(1)`

Common pitfalls

Using < instead of <= — equal values sneak in as an “increasing” step.
Thinking first, second must be the actual triplet — after an update, first may sit after second.
Looking only at adjacent elements — the triplet is a subsequence, not a subarray.

Interview tips

Explain why the stale first is fine: second alone certifies a smaller earlier value.
Present the prefix-min/suffix-max version first; it makes the “middle element” view concrete.
Mention the generalisation: this is LIS with patience sorting, stopped at length 3.

Pattern

Greedy smallest tails → detect an increasing subsequence of fixed length k in O(n·k) time and O(k) space.

My notes saved in this browser