Increasing Triplet Subsequence [Medium] — Greedy Two Trackers

Problem Statement

Given an integer array, return true if there exists a triplet of indices i < j < k such that nums[i] < nums[j] < nums[k].

Input: [1,2,3,4,5] → true
Input: [5,4,3,2,1] → false
Input: [2,1,5,0,4,6] → true

Intuition

Maintain first = smallest number seen, second = smallest number greater than some first. If we find any number > second, return true.

Solutions

C++

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

Java

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

JavaScript

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

Python

def increasingTriplet(nums: list[int]) -> bool:
    first = second = float('inf')
    for n in nums:
        if   n <= first:  first  = n
        elif n <= second: second = n
        else:             return True
    return False

Complexity

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