In a unsorted Array , At any point if we want Max/Min on either side of the element , We should think about using suffix array / prefix array .
Now in given problem ,
- The current element should be greater than all the elements on the left , [If we can get the max element till previous index , we can compare and conclude . i.e. if (maxLeft[i-1] < a[i]) then the condition passes.]
- Similarly for right side , get the minElem and check if its greater than a[i]. [ minRight[i+1] > a[i] ]
maxLeft - Prefix Array
minRight - Suffix Array