CareerCup

The problem can be solved in O(n).

Basically, at each index K you need to know if the largest element in A[0..K-1] is less than or equal to A[K], and if the smallest element in A[K+1..N-1] is greater than or equal to A[K].

Build two auxiliary arrays, mins and maxs, such that mins[i] stores the smallest element in array[i+1..N-1], and maxs[i] stores the largest element in array[0..i-1]. The auxiliary arrays can be built in O(N).

After building the auxiliary arrays, iterate through the array once more, looking for a position where maxs[K] <= array[K] and mins[K] >= array[K]. If found, return it; otherwise, if the loop ends, no such K exists.

Working implementation:

#include <iostream>
#include <limits>
#include <vector>

using namespace std;

vector<int>::const_iterator magnitude_pole(const vector<int> &arr) {

	if (arr.size() == 0) {
		return arr.end();
	}

	vector<int> mins(arr.size());
	vector<int> maxs(arr.size());

	mins[arr.size()-1] = numeric_limits<int>::max();
	maxs[0] = numeric_limits<int>::min();

	for (vector<int>::size_type i = 1; i < arr.size(); i++) {
		mins[arr.size()-1-i] = min(mins[arr.size()-i], arr[arr.size()-i]);
		maxs[i] = max(maxs[i-1], arr[i-1]);
	}

	for (vector<int>::size_type i = 0; i < arr.size(); i++) {
		if (maxs[i] <= arr[i] && mins[i] >= arr[i]) {
			return arr.begin()+i;
		}
	}

	return arr.end();
}

int main(void) {
	cout << "Enter number of elements in array followed by each element" << endl;
	cout << "> ";

	vector<int>::size_type elems;
	while (cin >> elems) {
		vector<int> array(elems);
		for (vector<int>::size_type i = 0; i < elems; i++) {
			cin >> array[i];
		}
		vector<int>::const_iterator mag_pole = magnitude_pole(array);
		if (mag_pole == array.end()) {
			cout << "No magnitude pole found." << endl;
		} else {
			cout << "Magnitude pole found at index " << mag_pole-array.begin() << endl;
		}
		cout << "> ";
	}

	return 0;
}

Lets start with an O(n2) solution.

1. Start from index 1 and iterate through n-1
2. Maintain Left(max) and Right(min) at any point of time
3. If the current element in question is >= Left(min) and <= Right(max) then it is a magnitude pole.
4. As we move right, update Left(max) as max of previous max and current value
5. Right(Min) will be changed iif next element = Right(min), essentially min element of the right list is going to be in the middle. in that case you will have to iterate through Right array to get next min.
Repeat steps till be reach second last element of the array.

The worst complexity is O(n^2) because of the need updating the min of right list.

I am thinking ways to avoid it. One solution could be to copy array into another array and sort it. That way you can know next min number from it, however you will need to maintain both min and max for left and right sub array.
With that it will be O(nLogn) time complexity with O(n) memory complexity

Any other suggestion?

I did both methods shown above.

In one with worst case O(n^2), I looped over the whole array looking poles that meet the criteria for left array elements (less than pole value). When found, I then check the right elements in an inner loop to make sure they are at least the value at the pole. If not, the outer loop moves to the next element. This returns the first valid pole only.

In the second with worst case O(n) but using more memory, I created 2 supporting arrays of the same size as the original. The first array will indicate which elements are valid poles using the left criteria (less than or equal pole value.) The values will be the same as original if that element is a pole that meets the criteria with all of the elements to its left. If not, the value will be -1. Similarly, the second array will indicate which elements are valid poles using the right criteria (all to the right are greater than or equal pole value). Again, the values in the array will be the same be the same as the original array if that element meets the right criteria (all elements to its right have values that are greater than or equal to that pole). A third and final loop in this second method loops over both generated arrays and picks out elements with the same index and value (ones with -1 are ignored). These elements represent all valid poles that meet criteria for elements to the left and right.

Ruby code, method 1:
def check_right(a,k)
  return true if k == a.size-1
  for i in k+1..a.size-1
    puts "i=#{i} COMP a[k]=#{a[k]} and a[i]=#{a[i]}"
    if a[k] <= a[i]
    else
      puts "CHECKFALSE"
      return false
    end
  end
  true
end

def look_pole(a)
  poles = []
  i=0
  max = a[i]
  k=0
  while i<a.size do
    puts "max=#{max} i=#{i} a[i]=#{a[i]}"
    if a[i] >= max
      puts "GREATER THAN OR EQUAL"
      # things are ok, check if right is ok
      if check_right(a,i)
        puts "RIGHT IS OK, POLE at i=#{i}"
        poles << i
      else
        puts "RIGHT NOT RIGHT"
        max = a[i]
      end
    else
      puts "LESS THAN"
    end
    i=i+1
  end
  return poles
end

a=[4,5,6,7,8]
a=ARGV[0].split(",").map {|i| i.to_i }
puts "pole position = #{ look_pole(a) }"
puts "#{a}"

run like this:
$ ruby find_pole1 4,2,3,2,4,6,10,11

Ruby code, method 2:
def find_pole(a)
   poles = []
   max = a[0]
   incr = []
   for i in 0..a.size-1
     if a[i] >= max
       max = a[i]
       incr[i] = max
     else
       incr[i] = -1
     end
   end

   min = a[a.size-1]
   decr= []
   for i in (a.size-1).downto(0)
     if a[i] <= min
       min = a[i]
       decr[i] = min
     else
       decr[i] = -1
     end
   end
   for i in 0..a.size-1
     poles << i if (incr[i] == decr[i]) && (incr[i] != -1)
   end
   puts "#{incr}\n#{decr}"
   return poles
end

a=ARGV[0].split(",").map {|s| s.to_i}
puts "#{a}"
p=find_pole(a)
puts "poles = #{p}"
n=[]
a.each_with_index {|x,i| n[i] = p.include?(i) ? x : 0}
puts "#{n}"

run like this:
ruby find_pole2 4,2,3,2,4,6,10,11

Very simple, with complexity O(n) and no extra array.

int findPole(const int * data, int n)
{
    if (n < 1)
        return - 1; 

    int poleIndex = 0; //current pole
    int poleValue = data[poleIndex]; //value at pole
    bool poleFound = true; //do we have pole

    for (int i = 1; i < n; i++)
    {
        if (poleFound)
        {
            if (data[i] >= poleValue) //still can be a pole
                continue;

            //not a pole anymore
            poleFound = false;

            //find max value from poleIndex to i
            while (++poleIndex < i)
            {
                if (data[poleIndex] > poleValue)
                    poleValue = data[poleIndex];
            }
        }
        else
        {
            //check if we have new pole
            if (data[i] >= poleValue)
            {
                poleIndex = i;
                poleValue = data[i];
                poleFound = true;
            }
        }
    }
    if (poleFound)
        return poleIndex;
    return -1;
}

Complexity O(n) and no extra space

int findPole(const int * data, int n)
{
    if (n < 1)
        return - 1; 

    int poleIndex = 0; //current pole
    int poleValue = data[poleIndex]; //value at pole
    bool poleFound = true; //do we have pole

    for (int i = 1; i < n; i++)
    {
        if (poleFound)
        {
            if (data[i] >= poleValue) //still can be a pole
                continue;

            //not a pole anymore
            poleFound = false;

            //find max value from poleIndex to i
            while (++poleIndex < i)
            {
                if (data[poleIndex] > poleValue)
                    poleValue = data[poleIndex];
            }
        }
        else
        {
            //check if we have new pole
            if (data[i] >= poleValue)
            {
                poleIndex = i;
                poleValue = data[i];
                poleFound = true;
            }
        }
    }
    if (poleFound)
        return poleIndex;
    return -1;
}

can there be multiple magnitude poles
eg. 4,3,2,1,5,6,7,8,9 poles are index no. with values 5,6,7,8,9
???

can there be  multiple magnitude poles
eg. 4,3,2,1,5,6,7,8,9 poles are index no. with values 5,6,7,8,9
???

int pole(int a[],int size)
{
int i,j;
int temp=a[0],c=2;
for(i=1;i<size;i++)
{
if(a[i]>=temp)
{
temp=a[i];
for(j=i+1;j<size;j++)
{
if(a[j]<a[i])
c=0;
}
if(c)
return i;
}
}
return -1;
}

int pole(int a[],int size)
{
        int i,j;
        int temp=a[0],c;
        for(i=1;i<size;i++)
        {
                if(a[i]>=temp)
                {      c=1;
                        temp=a[i];
                        for(j=i+1;j<size;j++)
                        {
                                if(a[j]<a[i])
                                        c=0;
                        }
                        if(c)
                                return i;
                }
        }
        return -1;
}

public static void findMagnitude(int[] a) {
		int min = Integer.MAX_VALUE, max = -1, mg_idx = -1, mg_val = -1;
		for (int i = 0; i < a.length; i++) {
			int t = a[i];
			if (t == mg_val) {
				continue;
			}
			if (t < mg_val) {
				mg_val = -1;
				mg_idx = -1;
			}
			if (t >= max && mg_val == -1) {
				mg_val = t;
				mg_idx = i;
			}
			if (t < min)
				min = t;
			if (t > max)
				max = t;

		}
		System.out.println(mg_idx);
	}
	public static void main(String[] args) {
		int[] a= {4,1,2,3,1,4,7,8,6,9};
		findMagnitude(a);
	}

O(n) without extra space

function array_pole($ar){
	$pole = $ar[0];
	$pole_idx = 0;
	$pole_flag = TRUE;
	
	for($i=1; $i<count($ar); $i++){
		if($ar[$i] >= $pole){
			if(!$pole_flag){
				$pole = $ar[$i];
				$pole_idx = $i;
				$pole_flag = TRUE;
			}
		}else{
			$pole_flag = FALSE;
		}
	}
	
	if($pole_flag){
		echo $pole_idx;
	}
}