Find an element in an unsorted array such that all left elements are smaller and all right elements are greater

Problem: Given an unsorted array, find an element before which all elements are smaller than it, and after which all are greater than it. Return index of the element if there is such an element, otherwise return -1.

For example:

Input: arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9}
Output: 4

All numbers after index 4 are bigger than the number at index 4 also all 
numbers before numbers at index 4 are smaller than it.

Method 1: The naive approach is to use two loops. One loop to select each element and other to compare it with all elements on left and all elements on right.
Time complexity: O(n²).

Method 2: We can solve this problem in O(n) using O(n) space complexity. Following is detailed approach:

• Create an auxiliary array. 
• Traverse input array from left to right and fill auxiliary_array such that  auxiliary_array[i] contains maximum element from 0 to i-1 in input array. 
• Traverse input array from right to left and keep track of minimum number. 
• The second traversal also finds the required element. 

#include <bits/stdc++.h>
using namespace std;

/* driver function */
int main()
{
    int arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9};
    int n = sizeof(arr)/sizeof(arr[0]);

    /* declaring auxilary array */
    int aux[n];

    /* filling the auxilary array such that aux[i] contains
       maximum of all elements from 0 - 1 */
    aux[0] = arr[0];
    for(int i = 1; i < n; i++)
    {
        aux[i] = max(arr[i], aux[i-1]);
    }

    /* declaring right min */
    int rightmin = arr[n-1], pos;


    for(int i=n-2; i>=0; i--)
    {
        /* check if we found a required element */
        if((rightmin > arr[i]) && aux[i-1] < arr[i])
        {
            pos = i;
            break;
        }

        /* updating rightmin */
        rightmin = min(rightmin, arr[i]);
    }
    cout<<pos<<endl;

    return 0;
}

Output:

4

Time Complexity: O(n) and Space Complexity: O(n)