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.

Which pattern this problem belongs to

The technique here is the two pointers pattern. A two pointers solution carries two markers forward through one array in a single pass, instead of nesting loops over every pair. Here the two markers are values rather than indices: the best candidate for the first element of the triplet, and the best candidate for the second.

The course Grokking the Coding Interview teaches that pattern and the array scans built on it. Our guide to recurring LeetCode patterns shows how much of an interview loop these one-pass array questions cover.

Hints

1. Greedy tracking:
   Checking every possible triplet would be too slow. Think instead about how you can track 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. A smaller candidate leaves more room 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 keeps second at the smallest possible candidate that can follow first.

3. Check for triplet:
   If the current number is greater than second, 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

• Always updating first with the smallest possible value gives the second element the widest set of candidates.
• Updating second to the smallest value greater than first lowers the bar a valid third element has to clear.
• When you finally encounter a number larger than second, three numbers must form an increasing sequence: first, second, and the current number.

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