c - Algorithm Issue -- Determine if array has already been partitioned (i.e. one step of quicksort) -

the last question on algorithms final has been driving me crazy past month. here question:

you have array a[0...n], write algorithm (in "proper" pseudocode) runs in o(n) can determine whether array has been partitioned relative index k , if so, find k; if not return -1;

to clarify, partition:

for each element e in a[0...n], if e < a[k] place e "left" of a[k], else put e "right" of a[k].

so example of partitioned array (w.r.t. k = 11):

a = [4 2 5 3 7 4 2 6 8 4 11010 10 20 11 15 13 28 99 11]

then

myalgo(a) -> (11) 

or

a = [10, 20, 30, 40, 11,100, 150, 101, 125]

then

myalgo(a) -> (5) 

but not:

a = [10, 20, 30, 40, 5]

myalgo(a) -> (-1) 

my first thought (which incredibly naive) awful literally can't put words. basically, inadvertently checked if array sorted , pulled random value out of middle.

my next thought scan list , first check find highest number hit before hitting decreasing number , ruling of numbers out... holding max , min , if things fall outside of both shifting possible partition index end of subset.

here tried (very, badly) implement (with test case):

int myalgo(const int* a, int n);  int main() {      const int a[] = {10, 20, 30, 40, 11, 100, 150, 101, 125};      int index;     if((index = myalgo(a, 9)) != -1) {         printf("a[%d] = %d", index, a[index]);     }     else {         printf("not partitioned >:/");     }      return 0; }  int myalgo(const int* a, int n) {     // index of smallest possible number in remainder of list     int minidx = 0;      // index of largest number we've encountered     int maxidx = 0;      // index of possible partition "center"     int kidx = 0;      bool ispart = false;      for(int i=0; < n; ++i) {         if( a[maxidx] <= a[i] )  {             maxidx = i;             if(ispart == false)  { kidx = i; minidx = i;} // if flipped time grab partitioner index             ispart = true;         }         else { ispart = false; minidx = i; }         printf("a[%d] = %d <==> a[%d]: %d : %c\n", maxidx, a[maxidx], i, a[i], (ispart?'t':'f'));         if( a[minidx] > a[i] ) { ispart = false; }         printf("a[%d] = %d <==> a[%d]: %d : %c\n", minidx, a[minidx], i, a[i], (ispart?'t':'f'));     }      printf("a[%d] = %d : %c\n\n", kidx, a[kidx], (ispart?'t':'f'));      // gotta check make sure valid list...     if(ispart) return kidx;     else return -1; } 

but, not surprisingly, output thus:

 a[0] = 10 <==> a[0]: 10 : t a[0] = 10 <==> a[0]: 10 : t a[1] = 20 <==> a[1]: 20 : t a[0] = 10 <==> a[1]: 20 : t a[2] = 30 <==> a[2]: 30 : t a[0] = 10 <==> a[2]: 30 : t a[3] = 40 <==> a[3]: 40 : t a[0] = 10 <==> a[3]: 40 : t a[3] = 40 <==> a[4]: 11 : f a[4] = 11 <==> a[4]: 11 : f a[5] = 100 <==> a[5]: 100 : t a[5] = 100 <==> a[5]: 100 : t a[6] = 150 <==> a[6]: 150 : t a[5] = 100 <==> a[6]: 150 : t a[6] = 150 <==> a[7]: 101 : f a[7] = 101 <==> a[7]: 101 : f a[6] = 150 <==> a[8]: 125 : f a[8] = 125 <==> a[8]: 125 : f a[5] = 100 : f                 <-- index right... ispart wrong
  
not partitioned >:/ 

i really able sleep tonight tips/hints/ideas/etc very, appreciated.

---

woo! @amit helped me solve issue, here updated function:

int partidx2(const int* a, int n) {      int* max = malloc(n * sizeof(int));     int* min = malloc(n * sizeof(int));      for(int i=0; < n; i++)     {         if(i==0) {             max[i] = a[i];             min[n - 1] = a[n-1];         }         else {             max[i] = max(max[i-1], a[i]);             min[n - 1 - i] = min(min[n - 1 - + 1], a[n - 1 - i]);         }     }      for(int i=1; < n-1; i++) {         if(a[i] >= max[i-1] && a[i] <= min[i+1]) {              free(max);             free(min);             return i;          }     }      free(max);     free(min);      return -1; } 

an o(n) time + space solution have 2 arrays, max , min.

max[i] = max{arr[0],arr[1],...,arr[i]} min[i] = min{arr[i],arr[i+1],...,arr[n-1]} 

note can create both arrays linear time.

after have these arrays, need find if there index k such that:

arr[k] >= max[k-1] && arr[k] <= min[k+1] 

this can done in linear time well

this works, because if above holds, each element after k guaranteed higher or equals arr[k], , each element before lower or equals arr[k], pretty definition of partition.