Increasing Triplet Subsequence

Increasing Triplet Subsequence

What is this problem about?

The Increasing Triplet Subsequence interview question asks you to determine if there exists a triple of indices $(i, j, k)$ in an array such that $i < j < k$ and $nums[i] < nums[j] < nums[k]$. Essentially, you need to find if there is an increasing subsequence of length 3. You want to solve this in $O(N)$ time and $O(1)$ space.

Why is this asked in interviews?

This is a classic optimization problem used by companies like Microsoft, Amazon, and Uber. It evaluates whether a candidate can move from a naive $O(N^3)$ or $O(N^2)$ approach to a highly efficient greedy strategy. It tests your ability to maintain multiple "state" variables that represent the best candidates found so far for an increasing sequence.

Algorithmic pattern used

This problem uses a Greedy interview pattern.

1. Maintain two variables: first and second, both initialized to infinity.
2. Iterate through the array:
   • If the current number is $\le first$, update first.
   • Else if the current number is $\le second$, update second.
   • Else (the number is greater than both), you have found your third element in the triplet! Return true. By keeping first and second as small as possible, you maximize your chances of finding a third number that completes the sequence.

Example explanation

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

1. 2: first = 2.
2. 1: first = 1 (found a smaller start).
3. 5: second = 5 (found a valid second element after 1).
4. 0: first = 0 (even smaller start! note: second is still 5, meaning we had a sequence ending in 5 previously).
5. 4: second = 4 (found a smaller second element after the implied first).
6. 6: 6 > 0 and 6 > 4. True! Triplet is (0, 4, 6).

Common mistakes candidates make

• Brute Force: Using a triple nested loop ($O(N^3)$).
• Misunderstanding Subsequence: Confusing subsequence with subarray (contiguous).
• Logical error: Thinking that if first is updated after second, the sequence is broken. In reality, second still represents the fact that some valid first existed before it.

Interview preparation tip

This problem is a specific case of the "Longest Increasing Subsequence" (LIS) problem. While the general LIS takes $O(N \log N)$, for a fixed length like 3, a greedy linear approach is superior. Always look for "Smallest candidates" in subsequence problems.