Increasing Triplet Subsequence – O(n) Java Solution

Given an integer array nums, determine whether there exists a triplet of indices (i, j, k) such that:

i < j < k

and

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

If such a triplet exists, return true. Otherwise, return false.

Example

Input:

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

Output:

true

Because we can find:

0 < 4 < 6

Another example:

[5, 4, 3, 2, 1]

Output:

false

There is no increasing sequence of three numbers.

Brute Force Approach

The simplest solution is to check every possible combination of three elements.

for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        for (int k = j + 1; k < nums.length; k++) {
            if (nums[i] < nums[j] && nums[j] < nums[k]) {
                return true;
            }
        }
    }
}

Although this works, it has:

Time Complexity: O(n³)

This can become very slow for large arrays.

We can solve the problem much more efficiently in O(n).

Key Idea

We maintain two variables:

first_num
second_num

Think of them as:

first_num  → smallest possible first number
second_num → smallest possible second number

Our goal is to find:

first_num < second_num < third_num

We scan the array only once.

Initialize

int first_num = Integer.MAX_VALUE;
int second_num = Integer.MAX_VALUE;

Initially, both values are set to the largest possible integer.

This allows the first numbers we encounter to replace them.

Find First

For every number n, first check:

if (n <= first_num) {
    first_num = n;
}

This means:

If we find a smaller number, make it our new first candidate.

For example:

Array = [5, 1, 2, 3]

After seeing 5:

first_num = 5

After seeing 1:

first_num = 1

Keeping 1 is better because a smaller first number gives us more opportunities to find an increasing triplet.

Find Second

If n is greater than first_num, we check:

else if (n <= second_num) {
    second_num = n;
}

Now we have:

first_num < second_num

We always try to keep second_num as small as possible.

For example:

first_num = 2
second_num = 10

If we encounter 5, we replace 10:

first_num = 2
second_num = 5

This is better because finding a number greater than 5 is easier than finding one greater than 10.

Find Third

The most important part is:

else {
    return true;
}

If we reach this condition, it means:

n > second_num

And we already know:

first_num < second_num

Therefore:

first_num < second_num < n

We have found our increasing triplet.

So we immediately return:

true

Dry Run

Consider:

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

When we reach 6:

0 < 4 < 6

Therefore:

true

Java Solution

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

        int first_num = Integer.MAX_VALUE;
        int second_num = Integer.MAX_VALUE;

        for (int n : nums) {

            if (n <= first_num) {
                first_num = n;

            } else if (n <= second_num) {
                second_num = n;

            } else {
                return true;
            }
        }

        return false;
    }
}

Why Greedy Works

The algorithm follows a greedy strategy.

We always try to keep:

first_num

as small as possible.

We also try to keep:

second_num

as small as possible.

Why?

Because smaller values make it easier to find the third value.

For example:

2 < 5

is more useful than:

2 < 10

because finding a number greater than 5 is easier than finding a number greater than 10.

Why Use <=?

The code uses:

n <= first_num

and:

n <= second_num

rather than <.

This is important because the sequence must be strictly increasing.

For example:

[1, 1, 1]

should return:

false

Equal values cannot form:

1 < 1 < 1

Using <= allows equal values to replace the current candidate without incorrectly considering them part of an increasing sequence.

Complexity

The array is scanned only once.

Therefore:

Time Complexity:

O(n)

Space Complexity:

O(1)

Only two variables are used regardless of the size of the input array.

Interview Explanation

A simple way to explain this solution in an interview is:

We scan the array once and maintain the smallest possible first and second elements of an increasing sequence. If we encounter a number greater than the second element, we have found an increasing triplet. Therefore, the solution runs in O(n) time and O(1) space.

Key Takeaway

The main pattern to remember is:

first < second < third

We maintain:

first  → smallest possible value
second → smallest possible value greater than first
third  → any value greater than second

As soon as we find:

number > second

we know that an increasing triplet exists.

return true;

Otherwise, after checking the entire array:

return false;

The final solution is:

Time  : O(n)
Space : O(1)

This is much more efficient than checking every possible triplet with three nested loops.