Increasing Triplet Subsequence

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.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Analyse:

First glance at the problem, I think of brute force, time complexity is O(n^3). Time limit exceeded.

 1 class Solution {
 2 public:
 3     bool increasingTriplet(vector<int>& nums) {
 4         if(nums.size() < 3) return false;
 5         
 6         for(int i = 0; i < nums.size() - 2; i++){
 7             for(int j = i + 1; j < nums.size() - 1; j++){
 8                 for(int k = j + 1; k < nums.size(); k++){
 9                     if(nums[i] < nums[j] && nums[j] < nums[k])
10                         return true;
11                 }
12             }
13         }
14         return false;
15     }
16 };

View Code

Then I come up with a o(n^2) solution, it is fix the first number, for the second number, I scan the array and keep recording a number that is larger than the first number, when the third number is found, return true. For exmaple, I have 3, 8, 7, 2, 0, 1, 4. Firstly, fix 3, second number is 8, when it scans to 7, second number becomes 7; keep scaning, when it comes to 2, since 2 is smaller than 3, doesn't update, second number is still 7. After one pass scan, nothing returned... Then fix 8, and repeat the same process.

 1 class Solution {
 2 public:
 3     bool increasingTriplet(vector<int>& nums) {
 4         if(nums.size() < 3) return false;
 5         
 6         for(int i = 0; i < nums.size() - 2; i++){
 7             int b = i + 1;
 8             while(nums[b] <= nums[i] && b < nums.size() - 1)
 9                 b++;
10             while(b + 1 < nums.size() && nums[b] >= nums[b + 1] && nums[b + 1] > nums[i])
11                 b++;
12             if(b == nums.size() - 1) continue;
13             int c = b + 1;
14             while(c < nums.size() && nums[b] >= nums[c])
15                 c++;
16             if(c == nums.size()) continue;
17             return true;
18         }
19         return false;
20     }
21 };

View Code

After all those tries, I gave a o(n) version.

 1 class Solution {
 2 public:
 3     bool increasingTriplet(vector<int>& nums) {
 4         if(nums.size() < 3) return false;
 5         
 6         int a = INT_MAX, b = INT_MAX;
 7         for(int i = 0; i < nums.size(); i++){
 8             a = min(nums[i], a);
 9             if(nums[i] > a) b = min(nums[i], b);
10             if(nums[i] > b) return true;
11         }
12         return false;
13     }
14 };