Increasing Triplet Subsequence — Solution

Problem

Given an integer array, determine whether there exist three elements at strictly increasing indices whose values are also strictly increasing. You only need to return true or false — not the triplet itself.

• Input: nums = [2, 1, 5, 0, 4, 6]
• Output: true
• Explanation: Values 1, 4, and 6 appear in left-to-right order and satisfy 1 < 4 < 6.

Counter-example: nums = [5, 4, 3, 2, 1] returns false because every element is smaller than the one before it, so no increasing triplet can exist.

Intuition

This is the length-3 case of the longest increasing subsequence problem. The greedy insight is that you only need two "candidate" values: the smallest element seen so far, and the smallest element that already has something smaller before it. Any element that exceeds both candidates immediately confirms a valid triplet.

Approach 1 — Precomputed Min/Max Arrays

For each index treated as the "middle" of the triplet, check whether a smaller element exists anywhere to its left and a larger element exists anywhere to its right.

Steps:

1. Build left_min where left_min[i] is the minimum of nums[0..i].
2. Build right_max where right_max[i] is the maximum of nums[i..n-1].
3. For each middle index j from 1 to n-2, check if left_min[j-1] < nums[j] < right_max[j+1].
4. Return True if any valid middle exists, otherwise False.

1def increasingTriplet(nums: list[int]) -> bool:
2    n = len(nums)
3    if n < 3:
4        return False
5
6    left_min = [0] * n
7    left_min[0] = nums[0]
8    for i in range(1, n):
9        left_min[i] = min(left_min[i - 1], nums[i])
10
11    right_max = [0] * n
12    right_max[n - 1] = nums[n - 1]
13    for i in range(n - 2, -1, -1):
14        right_max[i] = max(right_max[i + 1], nums[i])
15
16    for j in range(1, n - 1):
17        if left_min[j - 1] < nums[j] < right_max[j + 1]:
18            return True
19
20    return False

• Time: O(n) — three linear passes over the array.
• Space: O(n) — two auxiliary arrays of length n.

Approach 2 — Greedy with Two Candidates

Track first (smallest element seen) and second (smallest element with a valid smaller predecessor). Any element exceeding second immediately completes a valid triplet.

Steps:

1. Initialize first = second = +∞.
2. For each number, apply exactly one of three cases:
   • num ≤ first: update first — new global minimum.
   • num ≤ second: update second — better candidate middle element.
   • Otherwise: num > second > some earlier first, return True.
3. Return False if the loop ends without finding a triplet.

The non-obvious invariant: when first gets updated to a later, smaller value, second still encodes the promise that a valid (old_first, second) pair existed earlier in the array — so any future value greater than second genuinely completes a triplet.

1def increasingTriplet(nums: list[int]) -> bool:
2    first = second = float('inf')
3
4    for num in nums:
5        if num <= first:
6            first = num  # new global minimum, best candidate for first element
7        elif num <= second:
8            second = num  # valid middle element relative to some earlier first
9        else:
10            return True  # num > second, which itself had something smaller before it
11
12    return False

• Time: O(n) — single pass through the array.
• Space: O(1) — two scalar variables regardless of input size.

Complexity Summary

Common Mistakes

• Discarding second when first is updated: When a new minimum overwrites first, second remains valid because it was established relative to an earlier, larger first. The algorithm is correct even though first may now point to an index after second.
• Using strict < instead of <= when updating candidates: Changing num <= first to num < first breaks arrays like [1, 1, 1, 2] — the equal case should refresh first, not fall through to the second branch.
• Returning True when num == second: Equal values do not form a strictly increasing triplet, so num == second should update second, not trigger an early return — this is why the third else branch fires only when num > second.
• Treating first and second as a positionally valid pair at any moment: They are not always positionally ordered. first can advance to a later index while second holds a value from an earlier position. The logical invariant holds, but the raw indices may appear reversed.
• Skipping the n < 3 guard in the array approach: The loop accesses right_max[j + 1] with j up to n - 2, which requires at least 3 elements; a 2-element input causes an index out of bounds without the guard.

Related Problems

• longest-increasing-subsequence — the general form: find the longest increasing subsequence, of which this problem is the length-3 special case
• 3sum — also locates triplets satisfying a condition, but the constraint is a sum target rather than an ordering
• is-subsequence — verifying that elements appear in left-to-right order, the same positional constraint at the heart of this problem
• maximum-subarray — greedy linear scan that tracks the best accumulated state at each index, same algorithmic flavor
• non-overlapping-intervals — greedy candidate selection under an ordering constraint to maximize a count