 # 334. Increasing Triplet Subsequence

Updated: 2023-09-01 LeetCode problem

## Problem Statement

The task is to determine if the given list of numbers contains an increasing subsequence of length three. This means we need to find three indices i, j, and k in the list such that i < j < k and nums[i] < nums[j] < nums[k].

## Naive Solution

One possible naive solution is to use three nested loops to go through all possible triples in the list and check if they are increasing. But this solution is very inefficient, has a time complexity of O(n³), and does not meet the follow-up constraints of the problem.

## Approach

The given solution employs a smart iterative approach.

It uses two variables, first and second, initialized with infinity. As it goes through the list, it updates these variables with the smallest and second smallest numbers it has seen so far.

• If it finds a number larger than both, it means it has found an increasing triplet and returns True.
• If it finishes going through the list without finding such a number, it returns False.

This algorithm works because any number larger than first and second is effectively larger than at least two numbers before it in the list.

## Steps

• Initialize first and second to infinity.
• Iterate over nums. For each number n:
• If n is less than or equal to first, update first with n.
• Else, if n is less than or equal to second, update second with n.
• Else, return True.
• If you finish iterating without returning, return False.

## Python Solution

class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
# Initialize two pointers to track the smallest and second smallest elements
first = second = float('inf')

for n in nums:
# If the current number is smaller or equal than the smallest number found so far,
# then update the smallest number.
if n <= first:
first = n
# If the current number is greater than the smallest number but smaller or equal
# than the second smallest number found so far, then update the second smallest number.
elif n <= second:
second = n
# If the current number is greater than both smallest and second smallest numbers,
# it means we found a increasing triplet subsequence.
else:
return True
# If no increasing triplet subsequence was found, return False.
return False