Increasing Triplet Subsequence

medium array greedy

Problem

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Inputnums = [6, 1, 5, 2, 8]

Outputtrue

first=1, second=2, then 8 > 2 → triplet (1, 2, 8) exists.

nums (comma-separated)

def increasing_triplet(nums):
    first = second = float('inf')
    for x in nums:
        if x <= first: first = x
        elif x <= second: second = x
        else: return True
    return False

function increasingTriplet(nums) {
  let first = Infinity, second = Infinity;
  for (const x of nums) {
    if (x <= first) first = x;
    else if (x <= second) second = x;
    else return true;
  }
  return false;
}

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
        for (int x : nums) {
            if (x <= first) first = x;
            else if (x <= second) second = x;
            else return true;
        }
        return false;
    }
}

bool increasingTriplet(vector<int>& nums) {
    int first = INT_MAX, second = INT_MAX;
    for (int x : nums) {
        if (x <= first) first = x;
        else if (x <= second) second = x;
        else return true;
    }
    return false;
}

Explanation

We want to know if there are three positions, left to right, whose values strictly increase. Checking all triples would be slow, but we can do it in one pass by keeping just two running values: first (the smallest number seen) and second (the smallest number that has some smaller value before it).

Both start at infinity. For each value x: if x <= first we lower first; otherwise if x <= second we lower second (this x is bigger than some earlier first, so it can be the middle of a triplet); otherwise x is bigger than both, and we have found a third element greater than a valid second, so we return true.

The subtle part: even if first later gets overwritten by a smaller number, the fact that second was set means a valid first < second pair existed earlier in the array. So once any x > second appears, a real increasing triplet is guaranteed.

Example: nums = [6, 1, 5, 2, 8]. We set first = 6, then first = 1, then second = 5, then second = 2. When we reach 8 it is greater than second = 2, so the triplet (1, 2, 8) exists and we return true.

If we finish the loop without ever exceeding second, no triplet exists and we return false. Only two variables and one scan are needed.

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