Easy solution in C++ (O(n) time complexity)


#1

int Solution::perfectPeak(vector &A)
{
if(A.size()<=2)
{
return 0;
}
vectorleft(A.size(),0),right(A.size(),0);
int i,min_so_far=INT_MAX,max_so_far=INT_MIN;
for(i=A.size()-1;i>=0;i–)
{
int j=A.size()-i-1;
if(A[i]<min_so_far)
{
right[i]=1;
}
min_so_far=min(A[i],min_so_far);
if(A[j]>max_so_far)
{
left[j]=1;
}
max_so_far=max(max_so_far,A[j]);
}
for(i=1;i<A.size()-1;i++)
{
if(left[i]==right[i] && left[i]==1)
{
return 1;
}
}
return 0;
}