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.

2 comments:

  1. Please give review to this post
    http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html

    ReplyDelete
    Replies
    1. Good question and equally good answer..Enjoyed your post :)

      Delete