CareerCup

Step 1:
Scan the array from index 0 -> (N - 1) and keep track of the maximum value seen up to each index. Let's call it (max_value_seen) and it is initialized to the smallest value. At index i, if A[i] >= max_value_seen, then do two things:
1- max_value_seen = A[i]
2- potential_q[i] = true.
Where "potential_q" is an array of length N of booleans initialized to all false. When you say potential_q[i] = true, it means that index "i" is a potential candidate for "q" since it satisfies the first constaint, i.e., for all k < i, A[i] >= A[k].

Step 2:
Scan the array in reverse order and do the opposite, i.e., keep track of min value. Let say the min value is stored in "min_value_seen". At index j, do the following

if (A[i] <= min_value_seen) {
 min_value_seen = A[i];
 if (potential_q[i] == true)
	return i;
 }

If A[i] < min_value_seen, then for any j > i, A[j] \ge A[i]. Then if A[i] is a potential Q from previous section, we know that A[i] \ge A[k] for all k < i. As a result, Q = i is a solution.

Full code:

public class FindSubIndex {
    public FindSubIndex(int[] A) {
        this.A = A;
        
    }
    public int GetQ() {        
        boolean[] pot_q = new boolean[A.length];
        pot_q[0] = true;
        int max_value_seen = min_val;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > max_value_seen) {
                pot_q[i] = true;
                max_value_seen = A[i];
            }                
        }
        // if for some i, pot_q[i] = false, then Q cannot be i.
        int min_value_seen = max_val;
        if (pot_q[pot_q.length - 1])
            return A.length - 1;
        for (int i = 0; i < A.length; i++) {
            int rev_index = A.length - i - 1;
            if (A[rev_index] < min_value_seen) {
                min_value_seen = A[rev_index];
                if (pot_q[rev_index])
                    return rev_index;
            }
        }
        return -1;
    }
    private int[]       A;
    private int min_val = -(int) Math.pow(2, 32);
    private int max_val = (int) Math.pow(2, 32);
}

class Program {
 public static void Main(String arg[]) {
 int[] A = new int[]{....}.
 int Q = (new FindSubIndex(A)).GetQ();
 System.out.print(Q);
}

def findPivot(input):
	pivot = -1
	max = None
	for i in xrange(len(input)):
		if i == 0:
			pivot = 0
		elif input[i] < input[pivot] and pivot != -1:
			pivot = -1
		elif input[i] > max and pivot == -1:
			pivot = i

		if max == None:
			max = input[i]
		elif input[i] > max:
			max = input[i]

		
	return pivot

Memory O(2)
Time O(n)

I have a solution here: (not converted to code yet, but it should be simple)

All you need to do is fill 2 arrays, both of which having length n (lenght of the input array). One recording the greatest value seen so far, and the other recording the smallest value after that position, which is easier if we start the scan from the very end of the array.

For example,
input: [ 2, 3, 1, 4, 5, 6, 5 ]
1st array: [ 2, 3, 3, 4, 5, 6, 6 ] // start the scan at the beginning and keep track of max
2nd array: [ 1, 1, 1, 4, 5, 5, 5 ] // start the scan at the end and keep track of min

After we have these 2 array, we look for matching elements, which is 4 & 5 at index 3 & 4 respectively. These two are the possible index for choosing a pivot.

If no matches can be found, return -1:

input: [ 3, 2, 1 ]
1st: [ 3, 3, 3]
2nd: [ 1, 1, 1]
=> no match

This solution is correct because of the fact that, everything on the LHS of the pivot point is smaller than or equal to the pivot value, that is to say, the maximum value on the LHS of the pivot point is equal to the pivot value. Vice versa for minimum value on the RHS.

Hope this helps.

#import <stdio.h>

int solution(int A[], int N)
{
	int minind, maxind;
	int max = -2147483647, min = 2147483647;

	for (int i = 0; i < N; i++) {
		if (A[i] > max) {
			max = A[i];
			maxind = i;
		}
		if (A[i] < min) {
			min = A[i];
			minind = i;
		}
	}

	if (maxind < minind)
		return -1;

	max = -2147483647; min = 2147483647;

	for (int i = 0; i <= minind; i++) {
		if (A[i] > max)
			max = A[i];
	}

	for (int i = minind+1; i < N; i++) {
		if (A[i] < min)
			min = A[i];
	}

	if (max > min)
		return -1;

	int q = minind;

	for (int i = minind; i <= maxind; i++) {
		if (A[i] < max)
			q = i+1;
	}

	return q;
}

int main(int args, char **argv)
{
	int A[] = {4,2,2,1,4,6,7,8,9};

	printf("%d\n", solution(A, 9));
}

Not sure why we need to deal with 'expected' time. Algorithm is deterministic O( N ) time and space.

int pivot(int n, int* A)
{
	int pivot = -1;
	int* smaller = new int[n];
	int* greater = new int[n];
	
	greater[0] = A[0];
	for(int i=1; i < n; i++)		
		greater[i] = (A[i] > greater[i-1]? A[i]: greater[i-1]);
	
	smaller[n-1] = A[n-1];
	for(int i=n-2; i >= 0; i--)		
		smaller[i] = (A[i] < smaller[i+1]? A[i]: smaller[i+1]);	
		
	for(int i = 0; pivot == -1 && i < n; i++)
		if(greater[i]<=A[i] && smaller[i]>=A[i])
			pivot = i;	
		
	delete [] smaller;
	delete [] greater;
	
	return pivot;
}