How Many Times Has an Array Been Rotated, thesarfo

Given a sorted array that’s been rotated some unknown number of times, find how many rotations occurred. [4,5,6,7,0,1,2,3] → 4 rotations (the minimum element, 0, sits at index 4).

Key observation: the rotation count equals the index of the minimum element. Reuse the minimum-in-rotated-array logic, but track the index alongside the value.

public class Solution {
    public static int findKRotation(int []arr){
        int low = 0, high = arr.length - 1;
        int ans = Integer.MAX_VALUE, index = -1;

        while(low <= high){
            int mid = (low + high) / 2;

            if(arr[low] <= arr[high]){ // entire search space is already sorted
                if(arr[low] < ans){
                    index = low;
                    ans = arr[low];
                }
                break;
            }

            if(arr[low] <= arr[mid]){ // left part is sorted
                if(arr[low] < ans){
                    index = low;
                    ans = arr[low];
                }
                low = mid + 1;
            } else{ // right part is sorted
                if(arr[mid] < ans){
                    index = mid;
                    ans = arr[mid];
                }
                high = mid - 1;
            }
        }

        return index;
    }
}