Increasing Triplet Subsequence

Problem

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

Requirements

  • return whether an increasing subsequence of length 3 exists or not
  • Your algorithm should run in O(n) time complexity and O(1) space complexity.
  • 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.

Examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Given [1,20,5, 4,34,3,4,5]

Let's define an array of size two as follows
sub = [INT_MAX, INT_MAX, INT_MAX]

iterate through given
i = 0
sub = [1, INT_MAX, INT_MAX]

i = 1
sub = [1, 20, INT_MAX]

i = 2
sub = [1, 5, INT_MAX]

i = 3
sub = [1, 4, INT_MAX]

i = 4
sub = [1, 4, 34]

First Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int sub[] = {INT_MAX, INT_MAX};
        for (int e: nums) {
            if (e < sub[0]) {
                sub[0] = e;
            } else if (e < sub[1]) {
                sub[1] = e;
            } else {
                return true;
            }
        }
        return false;
    }
};

This fails for the following input.

1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]