Increasing Triplet Subsequence

Problem: Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example:

Input: nums = [2,1,9,8,4,7]
Output: true
Explanation: The triplet (1, 4, 5) is valid because nums[1] = 1 < nums[4] = 4 < nums[5] = 7.

Approach: The first thing which immediately comes to mind is to get the length of longest increasing subsequence in the array and if it is more than two then return true otherwise false but this will take O(n^2) time with linear extra space. Let's do better!

Here is the algorithm which is straight forward and really easy to understand:

• first = INT_MAX, second = INT_MAX
• FOR i = 0 to n:
• IF first >= nums[i] then first = nums[i]
• ELSE IF second >= nums[i] then second = nums[i]
• ELSE return true
• return false

That's all!

Implementation in C#:

        public bool IncreasingTriplet(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 2)

        {

            return false;

        }

        int first = int.MaxValue, second = int.MaxValue;

        for (int i = 0; i < length; ++i)

        {

            if (first >= nums[i])

            {

                first = nums[i];

            }

            else if (second >= nums[i])

            {

                second = nums[i];

            }

            else

            {

                return true;

            }

        }

        return false;

    }

Complexity: O(n)