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

Question

The last question on my algorithms final has been driving me crazy for the past month. Here is the question:

You have an array A[0...n], write an algorithm (in "proper" pseudocode) that runs in O(n) that can determine whether this array has already been partitioned relative to some index k and if so, find k; if not then return -1;

To clarify, by Partition:

For each element e in A[0...n], if e < A[k] place e to the "left" of A[k], else put e to the "right" of A[k].

So an example of a 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 was incredibly naive) was so awful I literally can't put it into words. Basically, it inadvertently checked if the array were sorted and pulled a fairly random value out of the middle.

My next thought was to scan the list and first check to find the highest number that I hit just before hitting a decreasing number and ruling all of those numbers out... basically holding a max and a min and if things fall outside of both then shifting my possible partition index to the end of my subset.

Here is where I tried (very, very badly) to implement this (with a 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) {
    // the index of the smallest possible number in the remainder of the list
    int minIdx = 0;

    // the index of the largest number we've encountered
    int maxIdx = 0;

    // index of possible partition "center"
    int kIdx = 0;

    bool isPart = false;

    for(int i=0; i < n; ++i) {
        if( A[maxIdx] <= A[i] )  {
            maxIdx = i;
            if(isPart == false)  { kIdx = i; minIdx = i;} // if we flipped then this is a good time to grab a 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'));

    // We gotta check this to make sure it is a valid list...
    if(isPart) return kIdx;
    else return -1;
}

But, not surprisingly, my output is 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                 <-- The index is right... but isPart is wrong

Not Partitioned >:/ 

I would really like to be able to sleep tonight so any tips/hints/ideas/etc would be very, very appreciated.

---

Woo! @Amit helped me solve my issue, here is my 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; i < 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 - i + 1], A[n - 1 - i]);
        }
    }

    for(int i=1; i < 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;
}

Answer 1

An O(n) time + space solution would be to have two arrays, max and min.

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

Note that you can create both arrays with linear time.

After you have these arrays, you need to find if there is an index k such that:

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

This can be done in linear time as well

This works, because if the above holds, then each element after k is guaranteed to be higher or equals to arr[k], and each element before it is lower or equals arr[k], which is pretty much the definition of partition.

Answer 2

Interesting problem

It seems to me that it must be possible to solve this without having to resort to extra buffer space.

We know that IF there is a pivot element, then

• all elements to the left of the (unknown) pivot position are less than or equal to the pivot element
• all elements to the right of the (unknown) pivot position are greater or equal to the pivot element

From this we know that

• all elements to the left of the pivot are less or equal to any element to the right of the pivot, and
• all elements to the right of the pivot are greater or equal to any element to the left of the pivot

A special case of this is that

• all elements to the left of the pivot are less or equal to the right-most element
• all elements to the right of the pivot are greater or equal to the left-most element

Using rationales like these, we should be able to recursively 'home in' on the pivot position, if there is one.

Pseudo-code:

Set highest value found on low side to value of first element
Set lowest value found on high side to value of last element
Set low index to first element
Set high index to last element
repeat
  increment low index
  if low index >= array length -> fail
  if value at new low index > highest so far on the low side
    set new highest-on-low-side value
      if new value greater than lowest value so far on right side,
        set low index back to what it was and mark it as stuck
        set highest-on-low-side value back to what it was
  decrement high index
  if high index < 0 -> fail
  if value at new high index < lowest so far on the high side
    set new lowest-on-high-side value
      if new value less than the highest value so far on the left side,
        set high index back to what it was and mark it as stuck
        set lowest-on-high-side value back to what it was
until both low and high index is stuck or until low index >= high index
if low index = high index
  pivot position = low index
else
  failure

Here's an actual Pascal implementation that I used to briefly verify this idea with a handful of test inputs, but I don't have time to do a full-fledged verification at the moment.

function PivotIndex(a: array of integer): Integer;
var
  HighestValueOnLeftSide: Integer;
  LowestValueOnRightSide: Integer;
  LowIndex: Integer;
  HighIndex: Integer;
  LowStuck, HighStuck: Boolean;
begin
  HighestValueOnLeftSide := -1;
  LowestValueOnRightSide := MaxInt;
  LowIndex := -1;
  HighIndex := length(a);
  LowStuck := False;
  HighStuck := False;
  repeat
    if not LowStuck then begin
      inc(LowIndex);
      if LowIndex >= length(A) then begin
        Result := -1;
        exit;
      end;
      if A[LowIndex] > HighestValueOnLeftSide then
        if A[LowIndex] > LowestValueOnRightSide then begin
          LowStuck := True;
          dec(LowIndex);
        end else
          HighestValueOnLeftSide := A[LowIndex];
    end;
    if not HighStuck then begin
      dec(HighIndex);
      if HighIndex < 0 then begin
        Result := -1;
        exit;
      end;
      if A[HighIndex] < LowestValueOnRightSide then
        if A[HighIndex] < HighestValueOnLeftSide then begin
          HighStuck := True;
          inc(HighIndex);
        end else
          LowestValueOnRightSide := A[HighIndex];
    end;
  until LowStuck and HighStuck or (LowIndex >= HighIndex);
  if LowIndex = HighIndex then
    Result := LowIndex
  else
    Result := -1;
end;

I'm sure this can be made more elegant and efficient, but let me know if you see any immediate problems with it.