How many times is a sorted array rotated?

Tutorial Level: Intermediate
In this lesson we will be solving a programming interview question to find out the number of rotations of a sorted array in O(log n) time using binary search.

[Thanapat]

for who don't understand modulo parts
case 1 if mid = 0 or the first index
for instance arr = [1, 2]
prev = mid - 1 = -1 which thrown an error because arr[-1] is out of range
prev = (mid - 1 + n) % n = 1, it prevent an error from negative index

case 2 if mid = n - 1 or the last index
such as arr = [2, 3, 1], assume that mid = 2
next = mid + 1 = 3, which arr[3] is out of range
next = (mid + 1) % n = 0, loop index is initialized to the first index, think like a circular array

hope you understand

[cyberpsybin]

If you cannot understand the modulo part; you can try this

mid = int(low + ((high - low) / 2))
# safely calculate previous and next indices
previous = max(0, mid - 1)
next = min(mid + 1, len(arr) - 1)

This should always keep your 'next' and 'previous' indices inside the (0, length - 1) range. Rest is taken case by the equalities used all over the code (<= and >=)

[ravindrabhatt]

We use a search similar to binary search (or DFS), for every mid element in the array that we find when end > start and check if the mid element satisfies the Pivot property. Eventually one of the mid element will satisfy it if the array is a sorted array. Get the index of the Pivot to determine the num of rotation.

The best performance will be O(1) and worst will be O(log n), Also we can have repetitions of same numbers but we can't really tell which of them is rotated.

[VoronweMagor]

No need to check the pivot property:

def sorted_rotations_bin(a):
L, R = 0, len(a) - 1
if R < 0 or a[L] < a[R]:
return 0
while R - L > 1:
M = (L + R) // 2
if a[M] < a[L]:
R = M
else:
L = M
if a[R] < a[L]:
return R
return L

[vandananayaknayak]

i am just revising these concepts, and you indeed are just amazing sir.! thanks a lot

[zhiyaowang]

Very well explained. It'd be great if you can do more of such videos!

[adarshverma]

One of the variation of the solution can be where we instead of checking the min element(and comparing two elements each time next and prev), as we can check for the maximum element in the array by just doing the one comparison as
if (inputs[mid] > inputs[mid + 1)
return mid + 1;
// Please refer the below code for the same.
public class SortedArrayRotated {
public static void main(String[] args) {
// int []inputs = new int[]{20, 30, 40, 50, 60, 70, 80, 90, 100, 10};
// int []inputs = new int[]{90, 100, 110, 10, 20, 30, 40, 50, 60}; // pivot element to break the recursion will be an element whose next number is smaller (ignoring the last index element).
int []inputs = new int[]{100, 110, 120, 130, 140, 50, 60};
int numberOfRotation = numberOfTimesSortedArrayIsRotated(inputs, 0, inputs.length - 1);
System.out.println(
numberOfRotation != 0 ?
"Inputs are rotated: " + numberOfRotation + " times" :
"Inputs are not rotated as it is in sorted format already"
);
}

private static int []inputs, int startIndex, int endIndex) {
if (startIndex > endIndex)
return 0;
int mid = (startIndex + endIndex) / 2;
if (mid != inputs.length - 1) {
if (inputs[mid] > inputs[mid + 1])
return mid + 1;
else // as we are not passing (mid - 1) for getting the left segment so we have to add this for the exit condition here.
if (mid == 0)
return 0;
else if (inputs[mid] < inputs[endIndex])
return numberOfTimesSortedArrayIsRotated(inputs, startIndex, mid); // here we have to include mid in taking the left segment becuase the check is only for comparing the next of mid
else
return numberOfTimesSortedArrayIsRotated(inputs, mid + 1, endIndex);
} else {
if (inputs[mid] < inputs[mid - 1])
return mid;
else
return 0;
}
}
}

[swaw]

Simple Solution to find without Pivot:
int findMin(vector<int>& nums) {
int start = 0;
int end = nums.size() - 1;
int number_of_times_rotated;

while(start <= end)
{
if(nums[start] <= nums[end])
{
number_of_times_rotated = start;
break;
}
else
{
int mid = (start + end) / 2;
if(nums[mid] < nums[end])
end = mid;
else
start = mid + 1;
}
}
return number_of_times_rotated;
}

[jameskelly]

To find the "pivot property", why do you need to check the next element? If prev is greater than mid, you've found your pivot.

[igboman]

def search_smallest(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] > arr[right]:
left = mid + 1
else:
right = mid
return left

found this in the book elements of the programming interview

[sahu]

I just have doubt regarding pivot statement A[mid] <= A[next] && A[mid] <= A[prev]) 

But i feel A[mid] < A[prev] && A[mid] < A[next]) is sufficient because there are no cases exist for ==, if no element is repeated.

Correct me if i am wrong.

But i understand in case of A[low] <= A[high], bcoz where A= { 1} then == condition is needed.
And for other case A[mid] <= A[high], bcoz where A= { 2, 1} means only 2 elements, then == condition helps here.same follows for A[mid] >= A[low].

[dankyt]

Final code in c++ which accepts duplicates and passes any test cases :-

int rotation(int a[], int n)
{
int low=0, high=n-1, mid;
while(low<=high)
{
if(low==high)
//For single element
return 0;

mid=low+(high-low)/2;
int next = (mid+1)%n;
int prev = (mid+n-1)%n;

if(a[mid]<=a[next] && a[mid]<a[prev])

return n-mid;
else if(a[mid]<=a[high])
high=mid-1;
else if(a[mid>=a[low]])
low=mid+1;
}
return 0;
}

[rishugoyal]

Nice Explanation... You left one case when our A[mid] comes out to be the largest element in the given array.. In this case A[mid] > A[prev] && A[mid] > A[next] ..and so we have found our minimum element which is A[mid+1]

[ugh]

We really only need to check one condition inside the loop: A[mid] > A[right]
if true the sub-array A[left .. mid] is sorted, update left = mid + 1
if false the sub-array A[mid .. right] is sorted, update right = mid
We are done when: left == right
This strategy will also handle duplicates.

[pranavganorkar]

Hi Animesh...can we write the case for a[mid] <= a[next] && a[mid] <= a[prev] as a[mid] < a[next] && a[mid] < a[prev] . Here as the array does not have duplicates, there is no point in checking for equality.

[ivandrofly]

Very simple/interesting problem (Learned before back in 2k17)

[sudarshansipu]

Hi..It was great video..Looks you have great expertise over B.S

Just one thing which i would say you rectify here is remove = from conditional statements as here duplicates is not possible as per your condition.At machine level it will optimise the code.

Thanx

[dingusagar]

def findMin(A, l, h):
if A[l] <= A[h]:
return A[l]
mid = int((l+h)/2)
return min([findMin(A, l, mid), findMin(A, mid+1, h)])
# same time complexity O(logn)

[ambarishguntupalli]

If the condition is that there are no duplicates, why are we using <= or >= inside the loop?

[abhishekguptasarma]

It feels so bad knowing such an amazing tutor will never upload another video 😥