How to approach for SADVAL?

general
1

Hi Everyone,
I am trying to solve SADVAL , But could not solve it in complexity less than O(n^2).

2

Suppose you fix the middle element. Then it is always best to take the minimum of all elements before it, and it is always best to take the immediately bigger value of all elements after it. To calculate the former for all elements, scan the array from left to right and just maintain the minimum value. To calculate the latter for all elements, scan the array from right to left and maintain a set of values, and use the function upper_bound.

3 Likes