LeetCode 334: Increasing Triplet Subsequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 334: Increasing Triplet Subsequence?

In LeetCode 334: Increasing Triplet Subsequence, you’re given an integer array nums, and your task is to determine if there exists a triplet (i, j, k) where i < j < k and nums[i] < nums[j] < nums[k]. The elements don’t need to be consecutive, just in increasing order by index. For example, in [1,2,3,4,5], [1,2,3] is a valid triplet, returning True. This problem tests your ability to detect an increasing subsequence, connecting to concepts in LeetCode 300: Longest Increasing Subsequence.

Problem Statement

• Input: An integer array nums.
• Output: A boolean—True if an increasing triplet exists, False otherwise.
• Rules:
• Triplet indices must satisfy i < j < k.
• Values must satisfy nums[i] < nums[j] < nums[k].
• Subsequence, not subarray (non-consecutive allowed).

Constraints

• 1 <= nums.length <= 5 * 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1

Examples

• Input: [1,2,3,4,5]
• Output: True (e.g., [1,2,3])
• Input: [5,4,3,2,1]
• Output: False (No increasing triplet)
• Input: [2,1,5,0,4,6]
• Output: True (e.g., [2,5,6])

Understanding the Problem: Finding the Triplet

To solve LeetCode 334: Increasing Triplet Subsequence in Python, we need to check if there’s any trio of numbers in nums that increases with their indices. A naive approach—checking all triplets—is O(n³), too slow for 5 * 10⁵ elements. Instead, we’ll use:

• Best Solution (Greedy Two-Pointer): O(n) time, O(1) space—fast and elegant.
• Alternative Solution (Brute Force): O(n³) time, O(1) space—simple but inefficient.

Let’s start with the greedy two-pointer solution, explained in a beginner-friendly way.

Best Solution: Greedy Two-Pointer

Why This Is the Best Solution

The greedy two-pointer approach is the top choice for LeetCode 334 because it’s efficient—O(n) time, O(1) space—and cleverly tracks just two values to detect a triplet in one pass. It maintains the smallest and second-smallest numbers seen so far, returning True as soon as a third larger number appears. It’s like keeping an eye out for a rising pattern—smart and quick!

How It Works

Think of this as a number scout:

• Step 1: Initialize Two Pointers:
• first = smallest number seen.
• second = second smallest number greater than first.
• Step 2: Scan Array:
• If num > second, found triplet (first < second < num).
• If num > first but < second, update second.
• If num < first, update first (still seeking larger second and third).
• Step 3: Why It Works:
• Greedy updates ensure we catch any triplet.
• Single pass avoids unnecessary comparisons.

It’s like spotting a rising trio step-by-step!

Step-by-Step Example

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

• Init: first = inf, second = inf
• 2: first = 2, second = inf
• 1: first = 1, second = inf
• 5: first = 1, second = 5
• 0: first = 0, second = 5
• 4: first = 0, second = 4
• 6: 0 < 4 < 6, return True
• Result: True

Example: nums = [5,4,3]

• 5: first = 5, second = inf
• 4: first = 4, second = inf
• 3: first = 3, second = inf
• End: No triplet, return False

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        # Initialize first and second smallest
        first = float('inf')
        second = float('inf')

        # Scan array
        for num in nums:
            if num > second:
                return True  # Found triplet: first < second < num
            elif num > first:
                second = num  # Update second smallest
            else:
                first = num  # Update first smallest

        return False  # No triplet found

• Lines 3-4: Start with infinity for first and second.
• Lines 7-12: Iterate:
• If num > second, triplet exists.
• If num > first, update second.
• Otherwise, update first.
• Line 13: Return False if no triplet.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—just two variables.

This is like a triplet-spotting eagle—swift and sharp!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute-force approach—O(n³) time, O(1) space—checks every possible triplet by iterating over all combinations of three indices. It’s the simplest way to understand the problem but far too slow for large inputs, making it a baseline for learning. It’s like combing through every trio—thorough but tedious!

How It Works

Check all triplets:

• Step 1: Triple nested loop over i, j, k.
• Step 2: Verify i < j < k and nums[i] < nums[j] < nums[k].
• Step 3: Return True if found, False otherwise.

Step-by-Step Example

Example: nums = [1,2,3]

• Triplets:
• (0,1,2): 1<2<3, True
• Result: True

Example: nums = [3,2,1]

• Triplets:
• (0,1,2): 3>2>1, False
• Result: False

Code for Brute Force Approach

Copy codeclass Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] < nums[j] < nums[k]:
                        return True
        return False

• Time Complexity: O(n³)—triple nested loops.
• Space Complexity: O(1)—no extra space.

It’s a triplet-checking slogger—basic but slow!

Comparing the Two Solutions

• Greedy Two-Pointer (Best):
• Pros: O(n) time, O(1) space, fast and scalable.
• Cons: Greedy logic less obvious.
• Brute Force (Alternative):
• Pros: O(n³) time, O(1) space, straightforward.
• Cons: Too slow for large n.

Greedy wins hands down.

Additional Examples and Edge Cases

• [1,2]: False (too short).
• [1,1,1]: False (no increase).
• [5,1,5,5,2,5,4]: True (e.g., 1,2,4).

Both handle these, but greedy is faster.

Complexity Breakdown

• Greedy Two-Pointer: Time O(n), Space O(1).
• Brute Force: Time O(n³), Space O(1).

Greedy is the clear choice.

Key Takeaways

• Greedy Two-Pointer: Spot the rise—efficient!
• Brute Force: Check all—simple!
• Python: Loops and logic shine—see [Python Basics](/python/basics).
• Subsequences: Triplets test order.

Final Thoughts: Find the Rise

LeetCode 334: Increasing Triplet Subsequence in Python is an array-traversal gem. The greedy two-pointer solution offers speed and elegance, while brute force provides a tangible baseline. Want more subsequence challenges? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 167: Two Sum II - Input Array Is Sorted. Ready to spot triplets? Head to Solve LeetCode 334 on LeetCode and rise to the challenge today!