## Saturday, August 24, 2013

### Find Nth largest element in the rotated sorted array

Question : Find Nth largest element in the rotated sorted array
So for example we have sorted array as  -
2,3,6,12, 15, 18.
Now suppose the array is rotated k times ( we don't know k), such that array becomes
15, 18,2,3,6,12

Solution
So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don't know. But seeing the above array we cans see that k = 2, which is also the index of minimum element i.e. 2 here. So, 3rd largest element is counting 3rd from 2 i.e. 6. Similarly for Nth largest element, it is k+N-1. But as we can see as the array is rotated, k+N-1 may overflow array, so we need to modulo operator on k+N-1, i.e. Nth largest element lies at = (k+N-1)%arraySize.

So, the problem breaks down in 2 step

1. Find k, i.e. number of rotations. To do so please refer the post - Find the rotation count in rotated sorted array
2. Return the arr[(k+N-1)%arr.size]

Here is the pseudocode:
```int findNthHigehest(int[] arr, int size, int n)
{
int k = findRotationCount(arr, size);
return arr[(n+k-1)%size];
}
```

Thanks.

1. 1. 