CareerCup

Hey folks. I think you are all missing a very important hint that the array is sorted and rotated by some K positions. In that case we should use the binary search principle to find the reset point, which will be the minimum element in the array. Below is the complete code to demonstarte this technique that runs in O(Log N) time:

#include <iostream>
using namespace std;
/* Find the reset point, i.e. the minimum element's index in 
   a sorted array that has been rotated (left or right) by some 
   number of positions.
*/
int find_reset_point(int arr[], int sidx, int eidx)
{
    int midx;
    if (eidx - sidx <= 0)
        return -1;
    while (sidx < eidx){
        if (eidx - sidx <= 1){
            if (arr[sidx] > arr[eidx])
                return eidx;
        }
        midx = sidx + (eidx - sidx) / 2;
        if (arr[midx] > arr[sidx])
            sidx = midx;
        else 
            eidx = midx;        
    }
    return -1; // No reset point detected, array is sorted ascending
}
int main(int argc, char *argv[])
{
    //int arr[] = {4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3};
    int arr[] = {10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    //int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int cnt = sizeof(arr)/sizeof(arr[0]);
    int idx;

    idx = find_reset_point(arr, 0, cnt - 1);
    cout << "IDX: " << idx << endl;

}

In case of ascending order, just find the first element which is less than its previous element.

for (i=1; i<n; i++)
{
    if (a[i] < a[i-1])
        return i;
}
return 0;  // in case when there is no rotation.

If the linked list is sorted in ascending order then find min in the array.
if the LL is sorted descending order find the maximum element.

we also have to take care of duplicate elements by using 2 pointers.

O(n) complexity.

Could someone tell me, what it means by 'rotating a LL'.

The solution in normal JavaScript (can be quickly written on browser, and executed:-), and following Binary Search:

//returns the starting point of an array-segment
var minList = function(arr) {
  var len = arr.length;
    //checks whether the array-segment is sorted
    if(arr[0] <= arr[len-1]) {
      return arr[0];  //returns the min value in an array-segment
    } else {
      //else continue till you find a sorted array segment
      var arr2 = arr.splice(arr.length/2);
      var min1 = minList(arr);
      var min2 = minList(arr2);
      return Math.min(min1,min2);
    }
};

just take the array a

the main point of this question is that if we take the mid point,either of the portion is sorted.We just have to pick the unsorted part and recursively find the point across which rotation exists.

//This approach gives you answer in n/2 steps. This function returns the index of the point where it is rotated
int func(int arr[])
{
int p1,p2;
for(p1=0, p2=arr.length-1; p1>=0,p2<arr.length; p1++,p2-- )
{
if(arr[p1]>arr[p1+1])
return p1;

if(arr[p2]<arr[p2-1])
return p2;

}
}

public static int findStartPoint(int [] array){
int left=0;
int right=array.length-1;

while (left<=right){
int mid=(left+right)/2;

if (array[mid]<array[mid-1]){
return mid;
}

if (array[mid]<array[left]){
right=mid-1;
}else if (array[mid]>array[right]){
left=mid+1;
}else if (array[mid]>array[left]&&array[mid]<array[right]){
return 0;
}

}

return -1;
}

struct listNode {
   int item;
   listNode * next;
}

listNode * findFirst(listNode * head) {
   listNode * currentMin = head;
   listNode * current = head;
   while (current != null) {
      if (current -> item < currentMin ->item) {
         currentMin = current;
      }
      current = current -> next;
   }
   return currentMin;
}