{x}
blog image

Increasing Triplet Subsequence

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.

 

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

 

Constraints:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

 

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Solution Explanation for Increasing Triplet Subsequence

The problem asks to determine if an integer array contains an increasing triplet subsequence—meaning three numbers nums[i], nums[j], and nums[k] such that i < j < k and nums[i] < nums[j] < nums[k].

The most efficient solution leverages a greedy approach with O(n) time and O(1) space complexity. This approach avoids nested loops, which would result in O(n^3) complexity.

Algorithm:

The core idea is to maintain two variables:

  1. min: Tracks the minimum number encountered so far.
  2. mid: Tracks the smallest number that's larger than min.

We iterate through the array. For each number:

  • If the number is greater than mid, we've found an increasing triplet, so we return true.
  • If the number is less than or equal to min, we update min to this number (it becomes the new smallest number).
  • Otherwise, the number is greater than min but less than or equal to mid. This means we've found a potentially better candidate for the middle element of our triplet, so we update mid.

If the loop completes without finding an increasing triplet, we return false.

Code Explanation (Python):

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        mi, mid = inf, inf  # Initialize min and mid to infinity
        for num in nums:
            if num > mid:  # Found the third number
                return True
            if num <= mi:  # Update min
                mi = num
            else:  # Update mid
                mid = num
        return False  # No increasing triplet found

Time and Space Complexity:

  • Time Complexity: O(n) - We iterate through the array once.
  • Space Complexity: O(1) - We use only a constant amount of extra space to store min and mid.

Code in other Languages:

The logic remains consistent across languages; only the syntax changes.

Java:

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int min = Integer.MAX_VALUE, mid = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > mid) {
                return true;
            }
            if (num <= min) {
                min = num;
            } else {
                mid = num;
            }
        }
        return false;
    }
}

C++:

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int mi = INT_MAX, mid = INT_MAX;
        for (int num : nums) {
            if (num > mid) return true;
            if (num <= mi)
                mi = num;
            else
                mid = num;
        }
        return false;
    }
};

Go:

func increasingTriplet(nums []int) bool {
	min, mid := math.MaxInt32, math.MaxInt32
	for _, num := range nums {
		if num > mid {
			return true
		}
		if num <= min {
			min = num
		} else {
			mid = num
		}
	}
	return false
}

TypeScript:

function increasingTriplet(nums: number[]): boolean {
    let min = Number.MAX_SAFE_INTEGER;
    let mid = Number.MAX_SAFE_INTEGER;
    for (let num of nums) {
        if (num > mid) {
            return true;
        }
        if (num <= min) {
            min = num;
        } else {
            mid = num;
        }
    }
    return false;
}

Rust:

impl Solution {
    pub fn increasing_triplet(nums: Vec<i32>) -> bool {
        let mut min = i32::MAX;
        let mut mid = i32::MAX;
        for num in nums {
            if num > mid {
                return true;
            }
            if num <= min {
                min = num;
            } else {
                mid = num;
            }
        }
        false
    }
}

All these code snippets implement the same efficient algorithm, achieving optimal time and space complexity.