# Solution by <644367822>

• #### Approach # 1 Brute Force [ Time Limit Exceeded ]

Algorithm

For each num of array (index from 1 to n - 1 ), we check whether index i meets such conditions

1 If it exist a index j (index from 0 to i - 1 ) Satisfies nums[j] < nums[i] - do condition 2 ,else next index i+1 .

2 If it exist a index k (index from i+1 to n ) Satisfies nums[j] > nums[i] return true ,else next index i+1 .

In the end ,if i == n return fasle .

c++

``````
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if( nums.size() < 3) {
return false ;
}
for( int i = 1 ; i < nums.size() - 1 ; i ++ ) {
bool find = false ;
for( int j = 0 ; j < i ; j ++ ) {
if( nums[j] < nums[i] ) {
find = true ;
break;
}
}
if( !find ){
continue ;
}
for( int k = i + 1 ; k < nums.size() ; k ++ ) {
if( nums[k] > nums[i] ) {
return true ;
}
}
}
return false ;
}
};

``````

Complexity Analysis

• Time complexity : \$O(N^2)\$.
• Space complexity : \$O(1)\$.

####Approach #2 Dynamic Programming [Accepted]

Algorithm

We can treat this problem as Longest Increasing Subsequence ,if the length of LIC >= 3 return true .

c++

``````

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> LIS;
for (int i = 0; i < nums.size(); i++) {
if (LIS.size() == 0 || LIS[LIS.size() - 1] < nums[i]) {
LIS.push_back(nums[i]);
}
else {
int l = 0, r = LIS.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (LIS[m] >= nums[i]) {
r = m;
}
else {
l = m + 1;
}
}
LIS[l] = nums[i];
}
}
return LIS.size();
}
bool increasingTriplet(vector<int>& nums) {
return lengthOfLIS(nums) >=3;
}
};

``````

Complexity Analysis

• Time complexity : \$O(N*logN)\$. Binary Search + Dynamic Programming
• Space complexity : \$O(N)\$.

####Approach #3 Scan and update [ Accepted ]

Algorithm

We scan the array from left to right and save the val used to record the first 2 elements of increasing size in an array.

c++

``````class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if( nums.size() < 3 ) {
return false ;
}
int a = nums[0] ;
int b = INT_MAX ;
for( int i = 0 ; i < nums.size() ; i ++ ) {
if( nums[i] <= a ) {
a = nums[i] ;
}
else {
if( nums[i] <= b ) {
b = nums[i] ;
}
else {
return true ;
}
}
}
return false ;
}
};
``````

Complexity Analysis

• Time complexity : \$O(N)\$.
• Space complexity : \$O(1)\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.