Easy to Understand O(n) solution!


#1

int Solution::perfectPeak(vector &A) {

int n = A.size();
vector<int> pre(n,0);
pre[0] = A[0];
vector<int> suff(n,0);
suff[n-1] = A[n-1];

for(int i=1;i<n;i++)
{
    pre[i] = max(pre[i-1],A[i]);
}

for(int i=n-2;i>=0;i--)
{
    suff[i] = min(suff[i+1],A[i]);
}

for(int i=1;i<n-1;i++)
{
    if((A[i] > pre[i-1]) && (A[i] < suff[i+1]))
    {
        return 1;
    }
}


return 0;

}