O(n) time O(1) space solution in C++


#1
int Solution::perfectPeak(vector<int> &A) {
if(A.size()<3) return 0;
int i = 1; int l = A[0];
while(i<A.size()-1) {
    if(A[i]>l) {
        l = A[i];
        int j = i+1;
        while(j<A.size())
        {
            if(A[j]<l)
            {
                i = j;
                break;
            }
            j++;
        }
        if(j==A.size()) {return 1;}
    }
    i++;
}
return 0;

}


#2

Hi @alde-hyde
I liked your approach however there is a bug in your code. It is failing on the following test case:
A : [ 1, 6, 9, 5, 7, 8 ]
Your Output: 1
Correct output: 0 (Coz there is no element satisfying the given condition)
Here is the correct code:

int Solution::perfectPeak(vector<int> &A) {
    if(A.size()<3) return 0;
    int i = 1; int l = A[0];
    while(i<A.size()-1) {
        if(A[i]>l) {
            l = A[i];
            int j = i+1;
            int pivot = l;
            while(j<A.size())
            {
                if(A[j]<=pivot)
                {
                    i = j;
                    break;
                }
                l = max(l, A[j]);
                j++;
            }
            if(j==A.size()) {return 1;}
        }
        i++;
    }
    return 0;
}

#3

this is O(N^2) and not O(N). Kindly check for all testcases.