Find the number of rotations in a circularly sorted array.
Medium
Find the number of rotations in a circularly sorted array. A circularly sorted array is an array that has been sorted in ascending order but then rotated, meaning that the elements at the end of the array have been moved to the beginning.
Write a function that determines the number of rotations the original sorted array has undergone.
Constraints
- The array contains distinct integers.
- The array may contain any number of elements, including an empty array.
Examples
arr = [4, 5, 1, 2, 3] output: 2 Explanation: the sorted array [1, 2, 3, 4, 5] has been rotated 2 times to become [4, 5, 1, 2, 3] arr = [1, 2, 3, 4, 5] output: 0 Explanation: the array is already sorted and has not been rotated, so the output is 0
Here’s how we can approach solving the "Find the number of rotations in a circularly sorted array" problem:
- Calculate the Length: First, determine the length of the input array.
- Handle Edge Cases: If the array is empty, return
0, as there are no rotations in an empty array. - Check if Array is Already Sorted: If the first element is less than or equal to the last element, return
0because the array has not been rotated. - Initialize Variables: Set up two pointers:
startandend, pointing to the first and last elements of the array, respectively. - Perform Binary Search: While
startis less thanend, calculate the midpoint. Use binary search to identify the point of inflection where the rotation occurs:- If
arr[mid]is greater thanarr[mid + 1], the inflection point is found, and the number of rotations ismid + 1. - If
arr[start]is less than or equal toarr[mid], the inflection point is in the right half, so movestarttomid + 1. - Otherwise, move
endtomid.
- If
- Return the Result: After the binary search completes, return
0if no rotation is found.
Here is the function implementation:
Time Complexity: The binary search operates in O(log n) time since we divide the search space in half with each iteration.
Space Complexity: The space complexity is O(1) since the algorithm only uses a constant amount of extra space.
Watch Simon Ayzman, a Principal Software Engineer @ Monarch Money find the number of rotations in a circular array.
