Rotation Count

Approach 1: Linear Search

Here, we could linearly traverse the entire array to find the minimum element and return its index.

Implementation

Let’s have a look at its implementation in Java -

import java.util.*;

class Coding Ninjas Studio{ 
    
    // find index of minimum element via Linear Search
    public static int RotationCount(int[] arr){
        int minidx = 0;
        int minno = arr[0];
        for (int i = 1; i < arr.length ; i++){
            if (arr[i] < minno){
                minno = arr[i];
                minidx = i;
            }
        }
        return minidx;
    }

    // Main Function 
    public static void main(String[] args){ 
        Scanner s = new Scanner(System.in);
        System.out.println("Enter size of the array");
        int n = s.nextInt();
        int[] arr = new int[n];
        
        System.out.println("Enter elements of the array");
        for (int i = 0; i < n; i++) arr[i] = s.nextInt();
        
        
        int rotations = RotationCount(arr);
        
        System.out.println("number of rotations: "+ rotations); 
   }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Time and Space Complexity

Time Complexity: O(n) where n is the length of the array, as the entire array needs to be traversed to find the index of the minimum element

Space Complexity: O(1) as no extra space has been used.
 

Now, let's discuss an optimised approach for finding the  index of the minimum element of the array i.e via BINARY SEARCH.

Approach 2: Binary Search

Since we know that the minimum element is the smallest element of the array, it would be smaller than both of its neighbors(left and right) in the array. We would use this property to find the index of the minimum element via Binary Search.

We know that the middle element of the array divides the array into two halves and it is worth mentioning that since the given array is a sorted rotated array, at least one of these halves will be sorted. We can use this property to determine the position of the minimum element of the array by deciding whether to discard the left or right half of the array on every iteration of binary search.

Algorithm

• Initialize lo and hi pointers denoting our current search space as lo = 0 and hi = n - 1, where n denotes the number of elements of the array.
• Run a while loop while lo <= hi(a valid search space)
  • If the left element of the current search space of array is less than or equal to the right element then the search space(subarray) being considered is sorted and we can directly return the left element as the minimum element.
  • Check if the middle element given by mid = lo + (hi - lo)/2 is the minimum element i.e arr[mid] is smaller than its left and right neighbours(arr[mid - 1] and arr[mid + 1]).
  • If the above step fails, then we need to reduce our search space for finding the position of the minimum element.
    • If the right half of the search space is sorted then we can discard the right half and move hi to mid - 1 as the middle element is not the minimum element and arr[mid...hi] is sorted.
    • Else the left half of the search space is sorted and we can discard the left half and move lo to mid + 1 as the middle element is not the minimum element and arr[lo...mid] is sorted with the left element being greater than the right element of the search space.

Note: If the middle element becomes the boundary element of the array, we take the right neighbour as the first element of the array if the middle element is the last element of the array and similarly the left neighbour is the last element of the array if the middle element is the first element of the array.

Implementation

Let’s have a look at its implementation in Java -

import java.util.*;

class Coding Ninjas Studio{ 
    
    // find index of minimum element via Binary Search
    public static int RotationCount(int[] arr, int low, int high){
        
        // If array is rotated => RotationCount = 0
        if (arr[low] < arr[high]) return 0;
 
        while (low <= high){
            // Finding mid via this to avoid overflow
            int mid = low + (high - low)/2;
            
            // handling corner cases
            int next = (mid + 1)%arr.length;
            int prev = (mid + arr.length - 1)%arr.length;
            
            // comparing both the neighbours
            if (arr[mid] <= arr[next] && arr[mid] <= arr[prev])
                return mid;
            
            // minimum element would lie in the left part
            else if (arr[mid] <= arr[high]) high = mid - 1;
            // minimum element would lie in the right part
            else if (arr[0] <= arr[mid]) low = mid + 1;
            
        }
        return -1; // any dummy value

    }

    // Main Function 
    public static void main(String[] args){ 
        Scanner s = new Scanner(System.in);
        System.out.println("Enter size of the array");
        int n = s.nextInt();
        int[] arr = new int[n];
        
        System.out.println("Enter elements of the array");
        for (int i = 0; i < n; i++) arr[i] = s.nextInt();
        
        
        int rotations = RotationCount(arr, 0, arr.length - 1);
        
        System.out.println("number of rotations: "+ rotations); 
   }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Time and Space Complexity

Time Complexity: O(logn) where n is the length of the array as in every iteration, the search space of the array gets reduced by half.

Space Complexity: O(1) as no extra space has been used.

Click here to know more about Array in Javascript here.

Frequently Asked Questions

1. What does the right rotation of an array mean?
   Ans. The right rotation of an array refers to the clockwise rotation of the elements of an array.
    
2. What is Binary Search? Explain.
   Ans: In Computer Science, Binary Search is a method for finding a target element in a sorted array by repeatedly dividing the search interval in half.
    
3. What are different algorithms for rotation of arrays?
   Ans. There are various algorithms for rotating arrays like Juggling Algorithm, Reversal Algorithm, Block Swap Algorithm, etc.
    
4. Which is faster, binary Search or linear Search?
   Ans: Binary search is faster than Linear Search as the worst-case time complexity of the linear search is O(n) while binary search has time complexity of O(log2n). 

Key Takeaways  

In this blog, we learned how to find the rotation count of a sorted and rotated array. 

• There are 2 approaches to find the rotation count: Linear Search and Binary Search.
• The main intuitive idea to find Rotation Count is finding the index of the minimum element of the array.
• The approach via Binary Search is more optimized than Linear Search as it has the worst-case time complexity of O(logn), but Linear Search has a time complexity of O(n). 
   

Recommended Problem - Merge K Sorted Arrays

Check out more blogs on different algorithms for Array Rotation to read more about these topics in detail. And if you liked this blog, share it with your friends!