Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

LeetCode 334 - Increasing Triplet Subsequence

Problem Understanding

The problem asks us to determine whether an array contains three numbers that form a strictly increasing subsequence. More specifically, we need to find indices i, j, and k such that:

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

The indices must appear in order, which means we are not allowed to rearrange the array. We only need to determine whether such a triplet exists, not return the actual indices or values.

The input is an integer array nums, and the expected output is a boolean value:

Return true if at least one increasing triplet exists
Return false otherwise

The constraints are important:

The array can contain up to 5 * 10^5 elements
Values can range from -2^31 to 2^31 - 1

These constraints immediately tell us that inefficient algorithms will not work. Any solution with O(n^2) or O(n^3) complexity will be far too slow for the largest inputs. The follow up explicitly asks for an O(n) time and O(1) space solution, which strongly suggests a greedy or state tracking approach.

Several edge cases are important to consider:

Arrays with fewer than three elements can never contain a triplet
Strictly decreasing arrays should return false
Arrays with duplicate values require careful handling because the comparison must be strictly increasing
The optimal subsequence may not use the smallest or largest values in the array
A valid triplet may appear after several misleading candidates

For example, in [2,1,5,0,4,6], the sequence 1 < 4 < 6 forms a valid triplet even though the array contains smaller values later.

Approaches

Brute Force Approach

The most direct solution is to check every possible triplet (i, j, k).

We can use three nested loops:

The first loop selects i
The second loop selects j > i
The third loop selects k > j

For each triplet, we verify whether:

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

If we ever find such a triplet, we return true. If all triplets are checked and none satisfy the condition, we return false.

This approach is correct because it exhaustively examines every possible combination of three ordered indices. However, it is extremely slow for large inputs.

With up to 500,000 elements, an O(n^3) algorithm is completely impractical.

Optimal Greedy Approach

The key insight is that we do not need to remember every subsequence candidate. We only need to track the best possible candidates for the first and second elements of an increasing triplet.

We maintain two variables:

first, the smallest value seen so far
second, the smallest value greater than first

As we scan through the array:

If the current number is smaller than or equal to first, we update first
Else if the number is smaller than or equal to second, we update second
Otherwise, we have found a number greater than both first and second, which means an increasing triplet exists

This works because keeping first and second as small as possible maximizes the chance of finding a larger third element later.

For example:

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

We progressively improve our candidates:

first = 1
second = 5
then first = 0
then second = 4
finally 6 > 4, so a triplet exists

This solution runs in linear time and uses constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triplet
Optimal	O(n)	O(1)	Greedily tracks smallest valid pair

Algorithm Walkthrough

Initialize two variables, first and second, to positive infinity.

These variables represent the smallest and second smallest values encountered so far that could form the beginning of an increasing triplet. 2. Iterate through each number in the array.

We process elements from left to right because index ordering matters. 3. If the current number is less than or equal to first, update first.

This means we found a better candidate for the smallest value in a potential triplet. 4. Otherwise, if the current number is less than or equal to second, update second.

At this point, we already know the number is greater than first, so it can serve as the second element of a triplet. We keep second as small as possible to maximize future opportunities. 5. Otherwise, the current number is greater than both first and second.

This means we have found:

first < second < current

Since elements are processed in order, the indices are also correctly ordered. We can immediately return true. 6. If the loop finishes without finding such a number, return false.

Why it works

The algorithm maintains an important invariant:

first is always the smallest value seen so far
second is always the smallest value greater than first

By greedily minimizing these two values, we maximize the chance that a later element can become the third value of an increasing triplet.

Whenever we encounter a number greater than both, we know a valid subsequence exists.

Python Solution

from typing import List
import math

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = math.inf
        second = math.inf

        for num in nums:
            if num <= first:
                first = num
            elif num <= second:
                second = num
            else:
                return True

        return False

The implementation begins by initializing first and second to infinity. This ensures that any real number in the array will replace them initially.

During iteration:

If num <= first, we update first
Else if num <= second, we update second
Otherwise, we have found a valid third element

The use of <= instead of < is important. Duplicate values cannot form a strictly increasing sequence, so duplicates should replace existing candidates rather than extend the subsequence.

The algorithm stops immediately once a valid triplet is found, which keeps the runtime efficient.

Go Solution

import "math"

func increasingTriplet(nums []int) bool {
    first := math.MaxInt
    second := math.MaxInt

    for _, num := range nums {
        if num <= first {
            first = num
        } else if num <= second {
            second = num
        } else {
            return true
        }
    }

    return false
}

The Go implementation follows the same logic as the Python version.

A few Go specific details are worth noting:

math.MaxInt is used instead of infinity
Go slices naturally handle empty arrays safely
Integer overflow is not a concern because we only perform comparisons
The range loop provides a clean way to iterate through the slice

Worked Examples

Example 1

nums = [1,2,3,4,5]

Step	Current Number	first	second	Action
1	1	1	inf	Update first
2	2	1	2	Update second
3	3	1	2	3 > second, return true

The algorithm finds the triplet 1 < 2 < 3.

Example 2

nums = [5,4,3,2,1]

Step	Current Number	first	second	Action
1	5	5	inf	Update first
2	4	4	inf	Update first
3	3	3	inf	Update first
4	2	2	inf	Update first
5	1	1	inf	Update first

No valid second or third element is ever found, so the result is false.

Example 3

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

Step	Current Number	first	second	Action
1	2	2	inf	Update first
2	1	1	inf	Update first
3	5	1	5	Update second
4	0	0	5	Update first
5	4	0	4	Update second
6	6	0	4	6 > second, return true

The valid triplet is 0 < 4 < 6.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only two extra variables are used

The algorithm performs a single pass through the array, making the runtime linear in the number of elements. No additional data structures proportional to input size are used, so the space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = float("inf")
        second = float("inf")

        for num in nums:
            if num <= first:
                first = num
            elif num <= second:
                second = num
            else:
                return True

        return False

solution = Solution()

assert solution.increasingTriplet([1, 2, 3, 4, 5]) is True  # simple increasing array
assert solution.increasingTriplet([5, 4, 3, 2, 1]) is False  # strictly decreasing
assert solution.increasingTriplet([2, 1, 5, 0, 4, 6]) is True  # valid triplet after reset
assert solution.increasingTriplet([1, 1, 1, 1]) is False  # duplicates only
assert solution.increasingTriplet([1, 2]) is False  # fewer than three elements
assert solution.increasingTriplet([1, 2, 2, 3]) is True  # duplicates with valid triplet
assert solution.increasingTriplet([20, 100, 10, 12, 5, 13]) is True  # non-contiguous triplet
assert solution.increasingTriplet([5, 1, 5, 5, 2, 5, 4]) is True  # multiple candidate replacements
assert solution.increasingTriplet([-5, -4, -3]) is True  # negative increasing sequence
assert solution.increasingTriplet([2, 4, -2, -3]) is False  # decreasing after positives

Test	Why
`[1,2,3,4,5]`	Basic increasing sequence
`[5,4,3,2,1]`	No increasing subsequence exists
`[2,1,5,0,4,6]`	Tests candidate replacement logic
`[1,1,1,1]`	Ensures duplicates are not treated as increasing
`[1,2]`	Array too small for a triplet
`[1,2,2,3]`	Verifies strict inequality handling
`[20,100,10,12,5,13]`	Non-adjacent triplet detection
`[5,1,5,5,2,5,4]`	Multiple updates to first and second
`[-5,-4,-3]`	Handles negative numbers correctly
`[2,4,-2,-3]`	Ensures false positives are avoided

Edge Cases

Arrays Smaller Than Length Three

An array with fewer than three elements can never contain a valid triplet. A naive implementation might forget this and accidentally return true due to incorrect initialization or comparison logic.

The current implementation naturally handles this case because the loop never finds a valid third element, so it returns false.

Duplicate Values

The sequence must be strictly increasing, meaning equal values cannot be reused.

For example:

[1,1,2,2,3]

A buggy implementation using only < comparisons during updates might incorrectly treat duplicates as progress toward a triplet.

The solution avoids this issue by using <= when updating first and second. This ensures duplicates replace existing candidates instead of extending the subsequence.

Resetting the Smallest Candidate

One subtle case occurs when a smaller value appears after a larger second candidate.

For example:

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

After seeing 1 and 5, we later encounter 0. A naive implementation might think the sequence is broken and discard progress incorrectly.

The greedy strategy handles this by updating only first while preserving the possibility of forming a better pair later. Eventually, 4 becomes the new second, and 6 completes the triplet.