C++ solution using two boolean arrays in O(n) time complexity!


#1

Create two boolean arrays “left” and “right”. “left” will store true for all those positions in array where the element is the maximum element seen so far. “right” array will store true for all those positions in array where the element is the smallest element from behind in that position. Now traverse the both boolean arrays simultaneously and check if there exist ‘true’ in same position. That index will be the peak of the array.
int Solution::perfectPeak(vector &A) {
int n=A.size();
bool left[n];
bool right[n];
left[0]=false;
right[n-1]=false;
int max_left=INT_MIN;
int min_right=INT_MAX;
for(int i=1,j=n-2;i<n && j>=0;++i,–j)
{
max_left=max(max_left,A[i-1]);
min_right=min(min_right,A[j+1]);
if(A[i]>max_left)
left[i]=true;
else
left[i]=false;
if(A[j]<min_right)
right[j]=true;
else
right[j]=false;
}
left[n-1]=false;
right[0]=false;
int c=0;
for(int i=0;i<n;++i)
{
if(left[i]==true && right[i]==true)
return 1;
}
return 0;

}