334. Increasing Triplet Subsequence - Detailed Explanation

Problem Statement

You are given an integer array nums. Your task is to determine whether there exists a triplet of indices (i, j, k) with i < j < k such that:

nums[i] < nums[j] < nums[k]

If such a triplet exists, return true; otherwise, return false. In other words, you need to check if there is an increasing subsequence of length three within the array.

Example 1

Input:

nums = [1, 2, 3, 4, 5]

Output:

true

Explanation:
An increasing triplet exists, for example, (1, 2, 3).

Example 2

Input:

nums = [5, 4, 3, 2, 1]

Output:

false

Explanation:
The array is strictly decreasing so no increasing triplet exists.

Example 3

Input:

nums = [2, 1, 5, 0, 4, 6]

Output:

true

Explanation:
An increasing triplet exists. One valid triplet is (1, 4, 6) where 1 < 4 < 6.

Constraints

• The array can be of any length, but an efficient solution should work in O(n) time.
• The extra space used should be O(1).
• The array may contain duplicate elements.

Hints

1. Greedy Tracking:
   Instead of looking for every possible triplet (which would be too slow), think about how you can keep track of a potential first and second element of the triplet while iterating through the array.

2. Maintain Two Variables:
   Use two variables, say first and second, that represent the smallest candidate for the first and second elements of an increasing triplet, respectively.

   • first: The smallest value seen so far.
   • second: The smallest value greater than first that you have seen so far.

3. Triplet Detection:
   Once you find an element that is greater than both first and second, you have your increasing triplet.

Approach: Greedy with Two Variables

Explanation

The idea is to iterate over the array once while maintaining two variables:

• first: Initially set to infinity (or a very large number), this variable stores the smallest value encountered so far.
• second: Also initially set to infinity, it stores the smallest value that is greater than first.

For each number in the array:

1. Update first:
   If the current number is less than or equal to first, update first with this number. This is because a smaller candidate gives a better chance to build an increasing sequence.

2. Update second:
   If the current number is greater than first but less than or equal to second, update second. This step ensures second is the smallest possible candidate that can follow first.

3. Check for Triplet:
   If the current number is greater than second, then you have found a number that can serve as the third element in the triplet. In that case, return true immediately.

If you finish iterating over the array without finding such a triplet, return false.

Why This Works

• By always updating first with the smallest possible value, you maximize the chance to find a valid candidate for the second element.
• By updating second to be the smallest value greater than first, you narrow down the requirements for a valid third element.
• When you finally encounter a number larger than second, it guarantees that there exist three numbers (namely first, second, and the current number) that form an increasing sequence.

Step-by-Step Walkthrough

Consider the array nums = [2, 1, 5, 0, 4, 6]:

1. Initialization:

   • Set first = ∞, second = ∞.

2. Iteration:

   • num = 2:
     • 2 ≤ ∞ → update first = 2.
     • first = 2, second = ∞.
   • num = 1:
     • 1 ≤ 2 → update first = 1.
     • first = 1, second = ∞.
   • num = 5:
     • 5 > 1 and 5 ≤ ∞ → update second = 5.
     • first = 1, second = 5.
   • num = 0:
     • 0 ≤ 1 → update first = 0.
     • first = 0, second = 5.
   • num = 4:
     • 4 > 0 and 4 ≤ 5 → update second = 4.
     • first = 0, second = 4.
   • num = 6:
     • 6 > 4 → an increasing triplet is found (0, 4, 6).
     • Return true.

Complexity Analysis

• Time Complexity: O(n) — The array is traversed once.

• Space Complexity: O(1) — Only two extra variables are used.

Python Code

Java Code