title: Find the element in an array, in which left elements are smaller and right elements are larger?
body: <p>Suppose if there's an array, find out the element left to which the elements are smaller and right to which the elements are larger. Else return -1. I know how to do this in O(n^2). But how can this be done in O(n)? </p>
  
  <p>The code for O(n^2): </p>
  
  <pre><code>#include &lt;iostream&gt;
  using namespace std;
  int main(){
  int array[] = {5, 1, 4, 3, 2, 8, 10, 7, 9};
  int sizeOfArray = sizeof(array)/sizeof(array[0]);
  for (int i = 1; i &lt; sizeOfArray-1; ++i) {
      int j = i-1;
      int k = i+1;
      while(array[j] &lt; array[i] &amp;&amp; array[k] &gt; array[i]){
          if(j == 0 &amp;&amp; k == sizeOfArray-1){
              cout &lt;&lt; array[i];
              return 0;
          }
          if(j&gt;0){
              j--;
          }
          if(k&lt;sizeOfArray){
              k++;
          }
  
      }
  }
  cout &lt;&lt; -1;
  return 0;
  }
  </code></pre>