The O(N) Increasing Triplet Subsequence Algorithm

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

Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:
Input: [1,2,3,4,5]
Output: true
Example 2:

Input: [5,4,3,2,1]
Output: false

Checking Increasing Triplet Subsequence in O(N) Algorithm

The most intutive solution will be to bruteforce a triplet in O(N^3) and see if it is in increasing order. Obviously, this is inefficient. A Better solution is to record the smaller numbers as iterating the array.

This greedy approach works, as we are iterating the array from left to the right. If we find out a number that is different than the two numbers we have found – and both numbers are smaller than the current number, we know it has a increasing triplet subsequence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, second = INT_MAX;
        for (const auto &n: nums) {
            if (n <= first) {
                first = n;
            } else if (n <= second) {
                second = n;
            } else return true;
        }
        return false; // can't find such triplet increasing subsequence
    }
};

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, second = INT_MAX;
        for (const auto &n: nums) {
            if (n <= first) {
                first = n;
            } else if (n <= second) {
                second = n;
            } else return true;
        }
        return false; // can't find such triplet increasing subsequence
    }
};

I have to say, this trick is elegant and makes the algorithm efficient in O(N) time and O(1) constant space. See implementation of Increasing Subsequence Triplet in Python: Teaching Kids Programming – Increasing Triplet Subsequence Algorithm

–EOF (The Ultimate Computing & Technology Blog) —