Mastering the Increasing Triplet Subsequence Problem in Python -LeetCode75

In the world of coding interviews and technical problem-solving, one problem that often challenges developers is the Increasing Triplet Subsequence on LeetCode . This problem tests your understanding of sequences, optimal traversal, and maintaining conditions using minimal extra space. It may seem straightforward at first glance, but solving it efficiently without brute force requires a strategic approach.

In this article, we will explore the Increasing Triplet Subsequence problem in detail, understanding what it asks, why it’s important, and how to solve it using a clean and optimal Python solution. We’ll walk through the logic, line by line, and help you understand the core idea behind the algorithm.

Problem Statement

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

• 0 <= i < j < k < nums.length
• nums[i] < nums[j] < nums[k]

In simple terms, the problem is asking: is there a subsequence of three numbers in the list that are strictly increasing and appear in that order?

Example 1:

Input: nums = [1, 2, 3, 4, 5]
Output: True
Explanation: The sequence 1 < 2 < 3 forms an increasing triplet.

Example 2:

Input: nums = [5, 4, 3, 2, 1]
Output: False
Explanation: No increasing triplet exists.

A naive approach would be to use three nested loops to check all combinations of triplets and verify if they satisfy the condition. However, this would result in a time complexity of O(n³)—which is extremely inefficient for large input sizes.

Instead, we want a solution that can solve the problem in linear time O(n) and constant space O(1). That’s where the optimal method shines.

Python Solution – Step-by-Step Explanation

Let’s now explore the optimal approach using the provided Python code:

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        
         if len(nums) < 3:
            return False

         min_val = float('inf')
         second_min_val = float('inf')

         for num in nums: 
            if num <= min_val:
               min_val = num
            elif num <= second_min_val:
               second_min_val = num
            else:
               # Found a triplet (min_val < second_min_val < num)
               return True

         # No triplet found
         return False

Let’s break this down step by step.

Step 1: Edge Case Check

if len(nums) < 3:
    return False

We first check if the length of the array is less than 3. If so, it is impossible to find a triplet, and we return False.

Step 2: Initialize Two Variables

min_val = float('inf')
second_min_val = float('inf')

We initialize two variables:

• min_val: Holds the smallest number found so far.
• second_min_val: Holds the second smallest number found after min_val.

By setting them to infinity, we ensure that any number in the list will be smaller during the first comparisons.

Step 3: Traverse the Array

for num in nums: 

We iterate over each number in the array once. Our goal is to adjust min_val and second_min_val appropriately based on the conditions below.

Step 4: Condition Checks

if num <= min_val:
    min_val = num

If the current number is less than or equal to the smallest seen so far (min_val), we update min_val. This means we found a new starting point for a potential triplet.

elif num <= second_min_val:
    second_min_val = num

If the current number is greater than min_val but smaller than or equal to second_min_val, then we update second_min_val. This means we may now have the first two parts of the triplet: min_val and second_min_val.

else:
    return True

If the current number is greater than both min_val and second_min_val, we have found an increasing triplet! We immediately return True.

Step 5: Return False if No Triplet Found

return False

If the loop completes without returning True, that means no increasing triplet was found in the array.

Why This Works

The cleverness of this algorithm lies in tracking just two values: the smallest and the second smallest elements that could potentially form the first two parts of the triplet. If a third number appears that is larger than both, we know that a valid increasing triplet subsequence exists.

This approach uses:

• O(n) time, since it iterates over the array once.
• O(1) space, since it only uses two extra variables.

This makes it a highly efficient solution.

Real-World Relevance

Understanding the Increasing Triplet Subsequence problem is not just an exercise in array traversal—it’s also a practical lesson in optimization and early exits. Problems like this appear in competitive programming, coding interviews, and real-world applications such as data stream analysis and financial trend detection.

Edge Cases to Consider

1. Duplicates: Arrays like [2, 1, 5, 0, 4, 6] still return True because the subsequence [1, 4, 6] is increasing.
2. Negative Numbers: The logic still holds; the comparisons are based on relative values, not absolutes.
3. Short Arrays: Arrays with fewer than 3 elements should always return False.

Conclusion

The Increasing Triplet Subsequence problem is a great example of how simple observations can lead to efficient algorithms. Instead of brute-forcing through combinations, we track just enough information to make smart decisions as we go.

If you’re preparing for technical interviews or want to sharpen your algorithmic thinking, mastering problems like this is essential. They help you learn how to identify patterns, reduce complexity, and write optimized code.

By understanding the logic and practicing the solution, you’re well on your way to handling a wide range of sequence and array-based problems in the future.

💡 Related Read: If you’re preparing for LeetCode-style problems, don’t miss our guide on Reversing Words in a String – A LeetCode 75 Problem Explained. It’s another must-know concept that often shows up in interviews.