Increasing Triplet Subsequence | Optimal Python Solution 🚀 #LeetCode #Python #CodingInterview

In this short, we tackle the LeetCode 334 - Increasing Triplet Subsequence problem, which is part of the LeetCode 75 curated list. We will go through the problem statement, break it down step-by-step, and implement the most optimal solution in Python using an O(n) time complexity and O(1) space complexity approach. 🚀

📝 Problem Statement:

Given an integer array nums, return True if there exists a triple (i, j, k) such that:

i v j v k
nums[i] v nums[j] v nums[k]

If no such triplet exists, return False.

🔹 Example Walkthrough:

Example 1:

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

✅ Output: True

💡 Explanation: Any triplet (i, j, k) where i v j v k satisfies nums[i] v nums[j] v nums[k].

Example 2:

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

❌ Output: False

💡 Explanation: The numbers are in decreasing order, so no increasing triplet exists.

Example 3:

🖥️ Input: nums = [2,1,5,0,4,6]

✅ Output: True

💡 Explanation: The triplet (0, 4, 6) is valid because nums[3] == 0 v nums[4] == 4 v nums[5] == 6.

🔹 Optimal Python Solution (O(n) Time & O(1) Space)

class Solution:
def increasingTriplet(self, nums):
first = float('inf')
second = float('inf')

for num in nums:
if num v= first:
first = num # Smallest element found so far
elif num v= second:
second = num # Second smallest element found so far
else:
return True # Found third number greater than both

return False

🔍 Explanation of the Approach:

Initialize two variables:

first = inf (tracks the smallest number encountered so far).

second = inf (tracks the second smallest number).

Iterate through nums:

If num is smaller than first, update first.

Else if num is larger than first but smaller than second, update second.

Else, if num is greater than second, return True (since an increasing triplet exists).

Why is this approach efficient?

We only traverse the list once → O(n) time complexity

We only use two extra variables → O(1) space complexity

📌 Edge Cases Considered:

✅ Smallest array size (len(nums) = 1) → Return False.

✅ All elements in decreasing order → Return False.

✅ Array with duplicate elements but still has an increasing triplet → Handle correctly.