C++ O(n) time and O(n) space complexity solution


#1

Keep a track of left maximum and right minimum array. While putting maximum and minimum, also check if maximum is same as the current element, if it is same, then put -1 in place of maximum and minimum arrays.
int Solution::perfectPeak(vector<int> &A) { int n = A.size(), big, sm; int max[n], min[n]; big = A[0]; sm = A[n-1]; for(int i = 0; i<n; i++){ if(A[i] == big){ max[i] = -1; continue; } if(A[i] > big) big = A[i]; max[i] = big; } for(int i = n-1; i>=0; i--){ if(A[i] == sm){ min[i] = -1; continue; } if(A[i] < sm) sm = A[i]; min[i] = sm; } for(int i = n-2; i>0; i--) if(max[i]==min[i] && max[i] != -1) return 1; return 0; }