Easy C++ in O(N) time complexity


#1

Maintain a minimum right array and maximum left array. Then if any element coincides in the same position in both the arrays and the count of its occurrence in each of the arrays is exactly equal to one, then that will be the answer.

int Solution::perfectPeak(vector &A) {

int n=A.size();
if(A.size()<3)
{
    return 0;
}
vector<int> right(n);
vector<int> left(n);
right[n-1]=A[n-1];
for(int i=n-2;i>=0;i--)
{
    right[i]=min(A[i],right[i+1]);
}
left[0]=A[0];
for(int i=1;i<n;i++)
{
    left[i]=max(A[i],left[i-1]);
}
for(int i=1;i<n-1;i++)
{
    if(right[i]==left[i])
    {
        if(right[i+1]!=right[i]&&left[i+1]&&left[i]&&right[i]!=right[i-1]&&left[i]!=left[i-1])
        {
            return 1;
        }
    }
}
return 0;

}