Array balancing point

Question

What is the best way to solve this? A balancing point of an N-element array A is an index i such that all elements on lower indexes have values <= A[i] and all elements on higher indexes have values higher or equal A[i].

For example, given:

A[0]=4 A[1]=2 A[2]=7 A[3]=11 A[4]=9

one of the correct solutions is: 2. All elements below A[2] is less than A[2], all elements after A[2] is more than A[2]. One solution that appeared to my mind is O(nsquare) solution. Is there any better solution?

Answer 1

Start by assuming A[0] is a pole. Then start walking the array; comparing each element A[i] in turn against A[0], and also tracking the current maximum.

As soon as you find an i such that A[i] < A[0], you know that A[0] can no longer be a pole, and by extension, neither can any of the elements up to and including A[i]. So now continue walking until you find the next value that's bigger than the current maximum. This then becomes the new proposed pole.

Thus, an O(n) solution!

In code:

int i_pole = 0;
int i_max  = 0;
bool have_pole = true;
for (int i = 1; i < N; i++)
{
    if (A[i] < A[i_pole])
    {
        have_pole = false;
    }
    if (A[i] > A[i_max])
    {
        i_max = i;
        if (!have_pole)
        {
            i_pole = i;
        }
        have_pole = true;
    }
}