Find the number of rotations in a circularly sorted array
Given a circularly sorted integer array, find the total number of times the array is rotated. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
For example,
Output: The array is rotated 3 times
Input: nums = [2, 5, 6, 8, 9, 10]
Output: The array is rotated 0 times
If we carefully analyze the problem, we can see that the total number of rotations is equal to the total number of elements before the minimum element, or the index of the minimum element.
A simple solution would be to run a linear search on the array and find the minimum element index. The problem with this approach is that its worst-case time complexity is O(n), where n is the size of the input. This solution also does not take advantage of the fact that the input is circularly sorted.
We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm. We have already reduced the problem to find out the first element of the sorted sequence. The first element (Pivot) has one special property (let’s call it the pivot’s property) – both the next and previous element of the pivot element are greater than it. No other array element will have this property except the pivot element. Since the array is circularly sorted,
- If the pivot is the last element, then the first element will be considered its next element.
- If the pivot is the first element, then the last element will be considered its previous element.
We know that the middle element always divides the array into two subarrays, and the pivot element can lie only in one of these halves. It is worth noticing that at least one of these subarrays will always be sorted. If middle element happens to be the point of rotation (minimum element), then both left and right subarrays are sorted. Still, in any case, one half (subarray) must be sorted, and we will use this property to discard the left half or the right half at each iteration of the binary search.
The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <stdio.h> // Function to find the total number of times the array is rotated int findRotationCount(int nums[], int n) { // search space is nums[low…high] int low = 0, high = n - 1; // loop till the search space is exhausted while (low <= high) { // if the search space is already sorted, we have // found the minimum element (at index `low`) if (nums[low] <= nums[high]) { return low; } int mid = (low + high) / 2; // find the next and previous element of the `mid` element // (in a circular manner) int next = (mid + 1) % n; int prev = (mid - 1 + n) % n; // if the `mid` element is less than both its next and previous // neighbor, it is the array's minimum element if (nums[mid] <= nums[next] && nums[mid] <= nums[prev]) { return mid; } // if nums[mid…high] is sorted, and `mid` is not the minimum element, // then the pivot element cannot be present in nums[mid…high], // discard nums[mid…high] and search in the left half else if (nums[mid] <= nums[high]) { high = mid - 1; } // if nums[low…mid] is sorted, then the pivot element cannot be present in it; // discard nums[low…mid] and search in the right half else if (nums[mid] >= nums[low]) { low = mid + 1; } } // invalid input return -1; } int main(void) { int nums[] = { 8, 9, 10, 2, 5, 6 }; int n = sizeof(nums) / sizeof(nums[0]); int count = findRotationCount(nums, n); printf("Array is rotated %d times", count); return 0; } |
Output:
Array is rotated 3 times
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
class Main { // Function to find the total number of times the array is rotated public static int findRotationCount(int[] nums) { // search space is nums[left…right] int left = 0; int right = nums.length - 1; // loop till the search space is exhausted while (left <= right) { // if the search space is already sorted, we have // found the minimum element (at index `left`) if (nums[left] <= nums[right]) { return left; } int mid = (left + right) / 2; // find the next and previous element of the `mid` element // (in a circular manner) int next = (mid + 1) % nums.length; int prev = (mid - 1 + nums.length) % nums.length; // if the `mid` element is less than both its next and previous // neighbor, it is the array's minimum element if (nums[mid] <= nums[next] && nums[mid] <= nums[prev]) { return mid; } // if nums[mid…right] is sorted, and `mid` is not the minimum element, // then the pivot element cannot be present in nums[mid…right], // discard nums[mid…right] and search in the left half else if (nums[mid] <= nums[right]) { right = mid - 1; } // if nums[left…mid] is sorted, then the pivot element cannot be present // in it; discard nums[left…mid] and search in the right half else if (nums[mid] >= nums[left]) { left = mid + 1; } } // invalid input return -1; } public static void main(String[] args) { int[] nums = { 8, 9, 10, 1, 2, 3, 4, 5, 6, 7 }; System.out.println("Array is rotated " + findRotationCount(nums) + " times"); } } |
Output:
Array is rotated 3 times
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
# Function to find the total number of times the list is rotated def findRotationCount(nums): # search space is nums[left…right] (left, right) = (0, len(nums) - 1) # loop till the search space is exhausted while left <= right: # if the search space is already sorted, we have # found the minimum element (at index `left`) if nums[left] <= nums[right]: return left mid = (left + right) // 2 # find the next and previous element of the `mid` element (in circular manner) next = (mid + 1) % len(nums) prev = (mid - 1 + len(nums)) % len(nums) # if the `mid` element is less than both its next and previous # neighbor, it is the list's minimum element if nums[mid] <= nums[next] and nums[mid] <= nums[prev]: return mid # if nums[mid…right] is sorted, and `mid` is not the minimum element, # then the pivot element cannot be present in nums[mid…right], # discard nums[mid…right] and search in the left half elif nums[mid] <= nums[right]: right = mid - 1 # if nums[left…mid] is sorted, then the pivot element cannot be present in it; # discard nums[left…mid] and search in the right half elif nums[mid] >= nums[left]: left = mid + 1 # invalid input return -1 if __name__ == '__main__': nums = [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] print(f'The list is rotated {findRotationCount(nums)} times') |
Output:
Array is rotated 3 times
The time complexity of the above solution is O(log(n)) and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)