NUHMAN.com

Introduction

LeetCode 334: Increasing Triplet Subsequence is a problem that challenges you to find if there exists a subsequence of length 3 in a given array of numbers such that the subsequence is strictly increasing. The task is to determine whether such a subsequence exists, and if so, return True, otherwise False.

This problem can be efficiently solved using a greedy approach where you track two potential candidates to form the triplet. The idea is to maintain the smallest and second smallest values seen so far and use them to check for the third increasing value.

Problem Statement

Given an integer array nums, return true if there exists an increasing subsequence of length 3 or more in the array, or false otherwise.

Note:

• Your solution should run in O(n) time complexity and use O(1) space complexity.

Example

python

Input: [1,2,3,4,5]
Output: True
Explanation: The subsequence [1,2,3] is an increasing subsequence.

Input: [5,4,3,2,1]
Output: False
Explanation: No increasing subsequence of length 3 exists.

✅ Approach: Greedy Algorithm

To solve this problem efficiently with O(n) time complexity and O(1) space complexity, we can use a greedy approach by maintaining two variables first and second:

• first tracks the smallest element.
• second tracks the smallest element that is greater than first.

Key Idea:

• Traverse through the array.
• If the current element is smaller than or equal to first, update first.
• If the current element is larger than first but smaller than or equal to second, update second.
• If the current element is larger than second, then we have found an increasing triplet subsequence.

This greedy approach works because we are trying to find the smallest possible first and second at each step, allowing us to form a valid triplet.

✅ Python Code

python

class Solution:
    def increasingTriplet(self, nums: list[int]) -> bool:
        first = second = float('inf')
        
        for num in nums:
            if num <= first:
                first = num  # Update the smallest number seen so far
            elif num <= second:
                second = num  # Update the second smallest number
            else:
                return True  # Found a number larger than both 'first' and 'second'
        
        return False

🧪 Dry Run Example

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

1. Initial Values: first = inf, second = inf
2. Iteration 1: num = 1

• num <= first → first = 1

1. Iteration 2: num = 2

• num > first and num <= second → second = 2

1. Iteration 3: num = 3

• num > second → Found an increasing triplet subsequence [1, 2, 3]
• Return True

Output: True

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(1)

• n is the number of elements in the array.
• We are making a single pass through the array, and only maintaining two variables (first and second), making it O(n) in time and O(1) in space.

🧠 Key Takeaways

• This problem demonstrates the power of the greedy algorithm in finding patterns like an increasing subsequence.
• Tracking two values (first and second) allows you to make decisions based on the current element, avoiding the need for nested loops or more complex algorithms.
• The O(n) time complexity and O(1) space complexity make this approach very efficient for large inputs.

🧱 Edge Cases

• Array of less than 3 elements: No triplet can be formed, so return False.
• Array with equal elements: No increasing subsequence exists, so return False.
• Array with an already increasing sequence: It will return True as soon as the third increasing number is found.

✅ Conclusion

LeetCode 334: Increasing Triplet Subsequence is a great example of how a greedy approach can solve a problem efficiently. By maintaining two variables (first and second), we can detect the existence of an increasing subsequence of length 3 in a single pass through the array. This solution is optimal in terms of both time and space complexity.