LeetCode [334] Increasing Triplet Subsequence

 334. Increasing Triplet Subsequence

Medium

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

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

bool increasingTriplet(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); for(int i=1; i<n; ++i){ for(int j=0; j<i; ++j){ if(nums[i]>nums[j]){ dp[i] = max(dp[i], dp[j]+1); if(dp[i]>=3) return true; } } } return false; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

bool increasingTriplet1(vector<int>& nums) { vector<int> dp; for(auto n:nums){ if(dp.empty()||n>dp.back()){ dp.push_back(n); if(dp.size()>=3) return true; }else{ int l = 0, r = dp.size()-1; while(l<=r){ int m = (l+r)/2; if((m==0||n>dp[m-1])&&n<=dp[m]){ dp[m]=n; break; }else if(n>dp[m]){ l = m+1; }else{ r = m-1; } } } } return false; }

1 2 3 4 5 6 7 8 9

bool increasingTriplet2(vector<int>& nums) { int c1 = INT_MAX, c2 = INT_MAX; for(auto n:nums){ if(n<=c1) c1 = n; else if(n<=c2) c2 = n; else return true; } return false; }