Code Implementation

class Solution:
    def increasingTriplet(self, nums):
        first = float('inf')
        second = float('inf')
        for n in nums:
            if n <= first:
                first = n
            elif n <= second:
                second = n
            else:
                return True
        return False
      

class Solution {
public:
    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;
    }
};
      

class Solution {
    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;
    }
}
      

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

Problem Description

Given an integer array nums, determine if there exists an increasing subsequence of length three (a triplet) such that nums[i] < nums[j] < nums[k] for some indices i < j < k.

Constraints:

• You must find whether any such triplet exists, not necessarily which one.
• Elements must be chosen in order (i.e., increasing indices), but do not need to be consecutive.
• Each element in the triplet must be a different value (no reuse of the same element).
• Return True if such a triplet exists, otherwise False.

Thought Process

At first glance, the problem asks if there is any sequence of three numbers in nums that are strictly increasing and appear in order. The most straightforward approach is to check all possible triplets, but this would be inefficient for large arrays.

To optimize, we can think about how to efficiently track potential candidates for the smallest and middle numbers as we traverse the array. If we can find two numbers that are smaller than a third encountered later, then we have our answer.

This leads to the idea of maintaining two variables: one for the smallest number seen so far (first), and one for the next smallest (second). If we ever find a number larger than both, we have found an increasing triplet.

Solution Approach

The optimized solution uses a single pass through the array and two tracking variables.

1. Initialize two variables: Set first and second to very large values (infinity).
2. Iterate through the array: For each number n in nums:
   • If n is less than or equal to first, update first (we found a new minimum).
   • Else if n is less than or equal to second, update second (we found a new "middle" value).
   • Else, n is greater than both first and second, so an increasing triplet exists. Return True.
3. If no such triplet is found after the loop, return False.

• By always updating first and second to the smallest possible values, we maximize the chance of finding a larger third number later.
• The conditions ensure that the indices are in order, and the values are strictly increasing.

Example Walkthrough

Let's use the input nums = [2, 1, 5, 0, 4, 6].

• Start: first = inf, second = inf
• n = 2: first becomes 2
• n = 1: first becomes 1 (new minimum)
• n = 5: 5 > 1, so check second; 5 <= inf, so second becomes 5
• n = 0: 0 < 1, so first becomes 0
• n = 4: 4 > 0, and 4 < 5, so second becomes 4
• n = 6: 6 > 0 and 6 > 4, so we have found our triplet (0, 4, 6)!

Time and Space Complexity

Brute-force approach:

• Check every possible triplet: O(n³) time, O(1) space.
• Not practical for large inputs.

• Single pass through array: O(n) time.
• Uses only two extra variables: O(1) space.
• This is much more efficient and scalable for large arrays.

Summary

The key insight is that we can efficiently track potential candidates for the smallest and middle values as we iterate through the array. By maintaining two variables and updating them appropriately, we can detect an increasing triplet subsequence in a single pass and constant space. This approach is both elegant and efficient, making it suitable for large datasets and real-world applications.