# Increasing Triplet Subsequence

Category

Array / String

Checkbox

Checkbox

Difficulty

Medium

Index

8

Key Ideas

The key idea to solve this problem is to keep track of the smallest two elements encountered so far and check if there is a third element greater than both of them.

Problem Number

334

Problem Summary

Given an unsorted array of integers, the "Increasing Triplet Subsequence" problem asks to determine if there exists a subsequence of length 3 in the array where the elements are in increasing order. A key pitfall is to mistakenly assume that finding three distinct numbers in increasing order is sufficient, when in fact the subsequence must be contiguous. Another pitfall is to use a brute force approach that involves checking all possible triplets, which has a time complexity of O(n^3) and is not efficient.

Solution Summary

The best solution to solve the Increasing Triplet Subsequence problem is to use a greedy approach. We initialize two variables,

`first`

and `second`

, with maximum possible values. We iterate through the array, and if we find a number smaller than `first`

, we update `first`

to that number. If we find a number greater than `first`

but smaller than `second`

, we update `second`

to that number. If we find a number greater than `second`

, we have found the increasing triplet subsequence and return `True`

. If we reach the end of the array without finding an increasing triplet subsequence, we return `False`

. This solution has a time complexity of O(n) and a space complexity of O(1).Tags

Array

Greedy