Array balancing point

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:开发者_Go百科 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?

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;
    }
}

If you want to know where all the poles are, an O(n log n) solution would be to create a sorted copy of the array, and look to see where you get matching values.

EDIT: Sorry, but this doesn't actually work. One counterexample is [2, 5, 3, 1, 4].

Make two auxiliary arrays, each with as many elements as the input array, called MIN and MAX. Each element M of MAX contains the maximum of all the elements in the input from 0..M. Each element M of MIN contains the minimum of all the elements in the input from M..N-1.

For each element M of the input array, compare its value to the corresponding values in MIN and MAX. If INPUT[M] == MIN[M] and INPUT[M] == MAX[M] then M is a balancing point.

Building MIN takes N steps, and so does MAX. Testing the array then takes N more steps. This solution has O(N) complexity and finds all balancing points. In the case of sorted input every element is a balancing point.

Create a double-linked list such as i-th node of this list contains A[i] and i. Traverse this list while elements grow (counting maximum of these elements). If some A[bad] < maxSoFar it can't be MP. Remove it and go backward removing elements until you find A[good] < A[bad] or reach the head of the list. Continue (starting with maxSoFar as maximum) until you reach end of the list. Every element in result list is MP and every MP is in this list. Complexity is O(n) since is maximum of steps is performed for descending array - n steps forward and n removals.

Update

Oh my, I confused "any" with "every" in problem definition :).

You can combine bmcnett's and Oli's answers to find all the poles as quickly as possible.

std::vector<int> i_poles;
i_poles.push_back(0);
int i_max = 0;
for (int i = 1; i < N; i++)
{
    while (!i_poles.empty() && A[i] < A[i_poles.back()])
    {
        i_poles.pop_back();
    }
    if (A[i] >= A[i_max])
    {
        i_poles.push_back(i);
    }
}

You could use an array preallocated to size N if you wanted to avoid reallocations.