Rotations in Circularly Sorted Array
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
Can you solve it in O(log n) time complexity?
Can you solve it in O(1) space complexity?
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:
from typing import List
def find_rotations(nums: List[int]) -> int:
start = 0
end = len(nums) - 1
if len(nums) == 0:
return 0
if nums[start] < nums[end]:
return 0
while start < end:
mid = start + (end - start) // 2
# Situation when midpoint is about the inflection point
if nums[mid] > nums[mid + 1]:
return mid + 1
if nums[start] < nums[mid]:
start = mid + 1
else:
end = mid
return 0Time 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.
Check out our lesson on the two-pointer approach to learn more about it and its applications!
Watch Simon Ayzman, a Principal Software Engineer @ Monarch Money find the number of rotations in a circular array.
function countRotations(arr, low, high) { if (high < low) { return 0; } if (high === low) { return low; } let mid = Math.floor((low + high) / 2); if (mid < high && arr[mid + 1] < arr[mid]) { return mid + 1; } if (mid > low && arr[mid] < arr[mid - 1]) { return mid; } if (arr[high] > arr[mid]) { return countRotations(arr, low, mid - 1); } return countRotations(arr, mid + 1, high); }