Interview - Find magnitude pole in an array

Question

Magnitude Pole: An element in an array whose left hand side elements are lesser than or equal to it and whose right hand side element are greater than or equal to it.

example input

3,1,4,5,9,7,6,11

desired output

4,5,11

I was asked this question in an interview and I have to return the index of the element and only return the first element that met the condition.

My logic

1. Take two MultiSet (So that we can consider duplicate as well), one for right hand side of the element and one for left hand side of the element(the pole).
2. Start with 0th element and put rest all elements in the "right set".
3. Base condition if this 0th element is lesser or equal to all element on "right set" then return its index.
4. Else put this into "left set" and start with element at index 1.
5. Traverse the Array and each time pick the maximum value from "left set" and minimum value from "right set" and compare.
6. At any instant of time for any element all the value to its left are in the "left set" and value to its right are in the "right set"

Code

int magnitudePole (const vector<int> &A) {  
   multiset<int> left, right;        
   int left_max, right_min;          
   int size = A.size();
   for (int i = 1; i < size; ++i)
       right.insert(A[i]);
   right_min = *(right.begin()); 
   if(A[0] <= right_min)
       return 0;
   left.insert(A[0]);
   for (int i = 1; i < size; ++i) {
       right.erase(right.find(A[i]));
       left_max = *(--left.end());
       if (right.size() > 0)
           right_min = *(right.begin());
       if (A[i] > left_max && A[i] <= right_min)
           return i;
       else
           left.insert(A[i]);
   }
   return -1;
}

My questions

• I was told that my logic is incorrect, I am not able to understand why this logic is incorrect (though I have checked for some cases and it is returning right index)
• For my own curiosity how to do this without using any set/multiset in O(n) time.

Answer 1

For an O(n) algorithm:

1. Count the largest element from n[0] to n[k] for all k in [0, length(n)), save the answer in an array maxOnTheLeft. This costs O(n);
2. Count the smallest element from n[k] to n[length(n)-1] for all k in [0, length(n)), save the answer in an array minOnTheRight. This costs O(n);
3. Loop through the whole thing and find any n[k] with maxOnTheLeft <= n[k] <= minOnTheRight. This costs O(n).

And you code is (at least) wrong here:

if (A[i] > left_max && A[i] <= right_min) // <-- should be >= and <=

Answer 2

• Create two bool[N] called NorthPole and SouthPole (just to be humorous.
• step forward through A[]tracking maximum element found so far, and set SouthPole[i] true if A[i] > Max(A[0..i-1])
• step backward through A[] and set NorthPole[i] true if A[i] < Min(A[i+1..N-1)
• step forward through NorthPole and SouthPole to find first element with both set true.

O(N) in each step above, as visiting each node once, so O(N) overall.

Answer 3

Java implementation:

Collection<Integer> magnitudes(int[] A) {
    int length = A.length;
    // what's the maximum number from the beginning of the array till the current position
    int[] maxes = new int[A.length];
    // what's the minimum number from the current position till the end of the array
    int[] mins = new int[A.length];

    // build mins
    int min = mins[length - 1] = A[length - 1];
    for (int i = length - 2; i >= 0; i--) {
        if (A[i] < min) {
            min = A[i];
        }
        mins[i] = min;
    }

    // build maxes
    int max = maxes[0] = A[0];
    for (int i = 1; i < length; i++) {
        if (A[i] > max) {
            max = A[i];
        }
        maxes[i] = max;
    }

    Collection<Integer> result = new ArrayList<>();
    // use them to find the magnitudes if any exists
    for (int i = 0; i < length; i++) {
        if (A[i] >= maxes[i] && A[i] <= mins[i]) {
            // return here if first one only is needed
            result.add(A[i]);
        }
    }
    return result;
}