Increasing Triplet Subsequence — LC 334 Greedy O(1) Space

Problem Statement#

Return true if there exists a triple of indices (i, j, k) with i < j < k and nums[i] < nums[j] < nums[k].

Constraints:

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

Input:  nums = [1,2,3,4,5]
Output: true

Input:  nums = [5,4,3,2,1]
Output: false

Why This Problem Matters#

LC 334 is a Facebook and Amazon favorite that looks like an LIS variant but rewards a much simpler insight. It teaches an important meta-skill: when you only need a fixed-length increasing subsequence, you can replace DP with O(1) trackers.

This array interview question separates candidates who memorize templates from those who think about state minimization. The trick generalizes to "k increasing" by maintaining k - 1 thresholds.

The Core Insight#

Track two values: first (smallest seen so far) and second (smallest value strictly greater than some earlier first). On each new number, update whichever is the smallest valid slot. If a value comes in that is greater than second, you have a triplet.

Crucially, you do not need to remember the original positions of first and second. Even if first updates to a later index than second, the invariant "there exists some earlier value smaller than second" still holds — because second was only set when there was a smaller first before it.

Visual Dry Run#

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

Solution (Optimal)#

class Solution:
    def increasingTriplet(self, nums: list[int]) -> bool:
        first = second = float("inf")
        for num in nums:
            if num <= first:
                first = num
            elif num <= second:
                second = num
            else:
                return True
        return False

var increasingTriplet = function(nums) {
    let first = Infinity, second = Infinity;
    for (const num of nums) {
        if (num <= first) {
            first = num;
        } else if (num <= second) {
            second = num;
        } else {
            return true;
        }
    }
    return false;
};

Time: O(n) — single pass. Space: O(1) — two variables.

Common Mistakes#

• Using < instead of <= and double-counting equal values.
• Trying to track indices and over-engineering the solution.
• Worrying that first updating after second invalidates correctness — it does not.
• Reaching for an LIS DP solution and writing O(n log n) when O(n) suffices.
• Forgetting strict inequality — [1,1,1] is not a valid triplet.

Interview Tips#

• Walk through the surprising case where first updates after second.
• Mention this is a special case of LIS with target length 3.
• Show O(1) space and explain why it is correct via invariants.
• If asked about k-length increasing subsequence, generalize to a list of k-1 trackers.

Follow-up Questions#

• Generalize to k-length increasing subsequence.
• Return the triplet itself, not just a boolean — track indices carefully.
• Allow non-strict <= — adjust comparisons.
• Find longest strictly increasing subsequence — use LC 300 patience sorting.
• Streaming version — same O(1) state works.

Key Takeaways#

• Two trackers first and second are sufficient for a length-3 check.
• Use <= so equal values do not falsely advance the tracker.
• Time is O(n), space is O(1) — no DP needed.
• The invariant holds even when first reassigns after second.
• Generalizes to k-length increasing via k - 1 trackers.
• Simpler than LIS for this specific question — pick the right tool.
• Common trap: overcomplicating with DP when greedy suffices.