# Just using the LIS to solve the problem in 8ms

• ``````class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int len=nums.size();
if(len<=3) return false;
return LIS(nums)>=3;
}

int LIS(vector<int> &nums){
int len=nums.size();
vector<int> result;
result.push_back(INT_MIN);
for(auto num:nums){
if(result[result.size()-1]<num)
result.push_back(num);
else {
int index=binarySearch(result, num);
result[index]=num;
}
}
return result.size()-1;
}

int binarySearch(vector<int>& nums, int target){
int start=-1, end=nums.size()-1;
int mid=0;
while(end-start>1){
mid=(start+end)/2;
if(nums[mid]>=target) end=mid;
else start=mid;
}
return end;
}
};``````

• Thanks the post from @alveko

We do not need to use the binary search to find the position as we only need to update for 3 position.

So we can optimize the TIME COMPLEXITY to O(N)

Here is the code:

``````class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int num1=INT_MAX, num2=INT_MAX;
for(int x:nums){
if(x<=num1){
num1=x;
}
else if(x<=num2){
num2=x;
}
else{
return true;
}
}
return false;
}
};``````

• This post is deleted!

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