Tags

, ,

I stumbled upon this question while interviewing for a company last week. It was in their written test and I tried to solve the question by finding the pivot by traversing linearly through the array.While this gives the answer, It takes a liner time i.e. the complexity depends on the length of array.

So how can we do it faster? Well we haven’t made use of all the information given to us. It is given that array is sorted and rotated.
So this is how I approached the question after coming back from interview process. I have a knack of finding answers after the interview is over. 

Lets first remove the edge cases : 
1. Array is already sorted and there is no pivot at all.  For e.g. 1 2 3 4 5
2. Pivot is at the end. For e.g. 2 3 4 5 1. 

So 1st corner case :
If array is already sorted then left most element will be smaller than right most element. Over. There we removed our first corner case.

2nd Corner case:
If pivot is at the end then element to the left of it will be greater than elements on its right and left.

So array[length-2] > array[length-1] and array[length -2] > array[length-3] 

The reason I removed these corner cases first is because these make my code looks cleaner.

Now lets delve into the main part.
lets suppose the array given to us is :      9 10 11 1 2 3 4 5 6 7 8

Clearly the pivot is 4th element.
So taking huge inspiration from binary search algorithm, we need to discard part of arrays which are sorted. Sorted part will not contain the pivot.(Think why ?)
So here is how I am discarding the sorted parts of array
if(array[mid] <= array[right])
        right = mid -1 ;
So mid = 5. (Because size of array is 11) 
       if(array[5]<array[10])   // totally satisfies as 3 is less than 8.
           right= 5-1

Now again calculating the mid. mid = 2.
      if(array[mid]<=array[right])
           right = mid -1;
Now this condition does not satisfy in this case. Hmmm lets check if the left part is sorted
     if(array[mid]>= a[left])
           left = mid+1; 
And drum rolls ! It satisfies our case. 

So lets write up the whole algorithm. I am avoiding the code as that can be written by you. 

int findPivot(int array[], int length)
{

     //checking for corner cases
     if(array[0]<array[length])
          return -1;
     if(array[length-2]>array[length-1] && array[length-2]>array[length-3])
         return length-1;

      //done with corner cases.
     int left,right,mid;
     left = 0;
     right = length -1;  
    while(left!=right)
    {
        mid = (left + right)/2;
         if(array[mid]<=array[right])
                right = mid -1;
         else if(array[mid]>=array[left])
                left = mid+1;

    }

    return mid;

}

 

I hope you enjoyed reading this. If you found any error in my algorithm or have some suggestion of solving it in a different manner please do comment.

Ciao.