Find Kth Rotation

Intuition

In a sorted rotated array, the minimum element is at index k (rotation count). Binary search for minimum element position.

Algorithm

1Binary search for the pivot (minimum element).
2If A[mid] > A[hi]: pivot is in right half. lo=mid+1.
3Else pivot in left half. hi=mid.
4Return lo (index of minimum = rotation count).

Common Pitfalls

•For sorted rotated array [3,4,5,1,2], rotation count = index of minimum = 3.

Find Kth Rotation.java

Java

// Approach: Binary search to find the index of the minimum element, which equals the rotation count.
// Time: O(log n) Space: O(1)
class Solution {
    public int findKRotation(int arr[]) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            if (arr[start] <= arr[end])
                return start;

            int mid = start + (end - start) / 2;
            int next = (mid + 1) % arr.length;
            int prev = (mid + arr.length - 1) % arr.length;

            if (arr[mid] <= arr[prev] && arr[mid] <= arr[next])
                return mid;
            else if (arr[mid] >= arr[start])
                start = mid + 1;
            else
                end = mid - 1;

        }
        
        return 0;
    }
}

Was this solution helpful?