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.

OR

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Examples

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.

Solution

Method 1 - Tracking first and second min

This problem can be transformed into checking if there’s a sequence where the_smallest_so_far < the_second_smallest_so_far < current. We use x, y, and z to represent these three numbers, respectively.

Here is the approach:

  1. Initialize Variables:
    • Use first_min to keep track of the smallest element so far.
    • Use second_min to keep track of the second smallest element so far.
    • Use potential_min to store a new minimum which might be the start of a new sequence.
  2. Iterate Through the Array:
    • If nums[i] is less than first_min, update first_min.
    • If nums[i] is greater than first_min but less than second_min, update second_min.
    • If nums[i] is greater than both first_min and second_min, return true.
    • Handle any new potential minimums and adjust the series accordingly.

Code

Java
public class Solution {

    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) {
            return false;
        }

        int firstMin = Integer.MAX_VALUE;
        int secondMin = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num <= firstMin) {
                firstMin = num; // Update firstMin if num is smaller
            } else if (num <= secondMin) {
                secondMin = num; // Update secondMin if num is larger than firstMin but smaller than secondMin
            } else {
                return true; // Found third number, return true
            }
        }
        return false; // No such triplet found
    }
}
Python
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False

        first_min = float('inf')
        second_min = float('inf')

        for num in nums:
            if num <= first_min:
                first_min = num  # Update first_min if num is smaller
            elif num <= second_min:
                second_min = num  # Update second_min if num is larger than first_min but smaller than second_min
            else:
                return True  # Found third number, return true

        return False  # No such triplet found

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)