# Leetcode 334 – Increasing Triplet Subsequence

#### Posted on February 28, 2016

##### Last updated on March 2, 2016

Problem link

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Suppose the elements that form the answer are a,b,c. The smallest element you ever encounter will be a. So if you see [1,-2,4,5], you first assign a to -1. Then look at -2. It can’t be the b, so update a to be -2. This is ok because if $$a_{new} < a_{old}$$ then any increasing subsequence that began with $$a_{old}$$ will still be an increasing subsequence after replacing $$a_{old}$$ with $$a_{new}$$ as $$a_{new} \lt a_{old}$$.

The following piece of code solves the problem:

Markdown SHA1: 04a74b961501d0914177825c7afdd8540cd1b3bf