Concept And Approach Without Code


#1

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 ,

  1. 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.]
  2. 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