# Find most of the O(n) submissions are actually O(n^2).Mine is truly O(nlgn) with binary search.

• Most of the O(n) (actually O(n^2)) submissions are from back to front. Mine is from front to the back.
e.p.For {8,10,4,6,1,3,5}, we actually process a problem like this:
We should test if the next number is in the 'segments':
4 is not in segments{8-10}
6 is the same, and expand the segments{4-6, 8-10}
1 is not in segments{4-6, 8-10}
3 is the same, and expand the segments{1-3, 4-6, 8-10}
5 is in the segments{4-6}
So return TRUE.
And this algorithm can use binary search.

``````typedef pair<int,int> p_type;
class Solution {
public:
bool find132pattern(vector<int>& nums) {
if(nums.size()<3)return 0;
deque<p_type>ds;
int m=nums[0];
for(int i=1;i<nums.size();i++)if(b_s(ds,nums[i],m))return 1;
return 0;
}
bool b_s(deque<p_type>&ds,int t,int&m){
int st=0,en=ds.size()-1;
int p=-1;
while(st<=en){
if(t<ds[st].first){p=st-1;break;}
if(t>ds[en].first){p=en;break;}
int mid=(st+en)/2;
if(ds[mid].first==t){p=mid;break;}
if(t>ds[mid].first)st=mid+1;
else en=mid-1;
}
if(p==-1){
if(t>m)ds.push_front(p_type(m,t));
else m=t;
}
else{
if(t>ds[p].first&&t<ds[p].second)return 1;
int p2=t>ds[p].second?t:ds[p].second;
ds.erase(ds.begin(),ds.begin()+p+1);
ds.push_front(p_type(m,p2));
}
return 0;
}
};
``````

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