[C++] | O(n) time complexity | Simple and detailed approach explained before the code

programming
Tags: #<Tag:0x00007f243555e780>

#1

First, we will find those elements which are strictly greater than all the elements on its left. Then we will traverse from back to the start and look for those elements which are strictly smaller than all the elements on its right, if it was also greater than all the elements on its left then return 1, else if there is no element like this then return 0.

In the following code, the temp will store position of those elements which are greater than all the elements on its left.

int Solution::perfectPeak(vector<int> &A) {
    int n = A.size();

    //Finding elements which are strictly greater than those in its left.
    int mx = A[0];
    vector<int> temp(n, 0);
    for(int i=1; i<n; i++)  {
        if(A[i]>mx) {
            temp[i] = 1;
            mx = A[i]; 
        }
    }

    //Looking for elements which are strictly smaller than elements in its right.
    int mn = A[n-1];
    int ans = 0;
    for(int i=n-2; i>=0; i--)   {
        if(A[i]<mn) {
            if(temp[i]==1)  { //If it was also greater than all the elements on its left
                return 1;
            }
            mn = A[i];
        }
    }
    return 0;
}