How many times is a sorted array rotated?
Vložit
- čas přidán 7. 09. 2024
- 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.
Prerequisite: Knowledge of binary search algorithm. Watch previous lessons here - • Binary Search
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
Thanks a lot!! This was really required! 🙏
Well explained👍🏻
Thanks
you all prolly dont give a shit but does any of you know a way to log back into an instagram account..?
I stupidly lost the password. I would love any tricks you can give me
@Ray Eugene Instablaster ;)
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 (=)
Thanks for noticing Sudarshan !!
Very well explained. It'd be great if you can do more of such videos!
i am just revising these concepts, and you indeed are just amazing sir.! thanks a lot
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.
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.
true
what if your next element is greater ? that's why pivot property
@@vinaypednekar680 then it would not be a circularly sorted array
True, I don't think there is any need to check the next element, checking prev element is enough.
Wt you said is correct
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 numberOfTimesSortedArrayIsRotated(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;
}
}
}
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
I just have doubt regarding pivot statement A[mid]
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
Hi @Saurav Kumar , it seems it is not working: For example input is : 5, 6,7, 1, 2,2, 3,3,3, 4 No of rotations = 3, but your code is not giving correct answer
Hi Animesh...can we write the case for a[mid]
to solve edge cases like
if there is one array
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]
It feels so bad knowing such an amazing tutor will never upload another video 😥
Dude he's not dead his colleague is
@@vikramadityavardhan4067 what's channel owner name?
Simple Solution to find without Pivot:
int findMin(vector& nums) {
int start = 0;
int end = nums.size() - 1;
int number_of_times_rotated;
while(start
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
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.
hmm nice one.more efficient
14,16,18,20,2,4,6,8,10,12
in you case it will take 3 iteration, while with his logic only one iteration is required. If size of array is large then your logic will take more time compared to his. Correct me if i'm wrong.
@@aakash4351 it is still O(logn)
Very simple/interesting problem (Learned before back in 2k17)
If the condition is that there are no duplicates, why are we using = inside the loop?
think when low = high
e.g. Array = [1]
@@ShivamAroraa I think we need
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
Thank you so much broo u have clarified my all the doubts
@mycodeschool was, is, & will be the best channel ever!
What is the use of taking A[low]
consider the case where array is --> [1]
This case is when array rotated zero times
Hi just wondering that you said the condition set is "no duplicates" then why are you checking in case 1 that A[low]
no, in worst case, low and end index can simultaneously reach the pivot. for that case we need to write a[low]
@@neerajjoshi9493 I didn't get you. Can you explain more clearly?
@@sarthakjoshi3797
consider the case where array is --> [1]
hey can anyoe explain me whats the reason for (mid+1)%n? and also (A[mid]
suppose,for an array of size n, mid=n-1, if you do only next=(mid+1) then it will be, next=n. Which is not possible! So, to avoid this type of situation it is done as next=(mid+1)%n. So, when mid=n-1, the next element will be 0th element.
And yes, only A[mid]
@@rpodder actually mid=n-1 case comes only when l=n-1 h=n-1, in this case, the first case if(A[l]
@@alphazero0 Oh, yes. What you said is correct. 👏
@@rpodder and whats the reason for A[mid]
thanks. great explanations
for this type of input {1,4,6,7,8,12,13,14,5} it goes in first case and return rotation count =0. which is actually the case for sorted array with no rotation. But basically the input is not correct.
def findMin(A,l,h):
if A[l]
Thank you so much
is the modulo part even necessary? the while loop runs 'while' low
the modulo part is necessary. for instance, take array having two elements {15,10} and perform dry run by yourself (not by compiler) you will get your answer. answer of this particular example should be 1.
Then take array of three elements, for instance [5,10,2]. again do dry run by yourself. answer for this one is 2.
BY THE END YOU WILL GET WHY MODULO WAS USED IN BOTH(PREV AND NEXT) STATEMENT.AND ALSO THE REASON OF ADDING n INSIDE BRACKET IN prev=(mid+n-1)%1. array of these length is just an example
Great Explanation but the fourth case mentioned if(A[mid] >= A[low] is wrong. It should be A[mid] >= A[high].
Srikanth s No, this is right.
See the condition:
if (A[mid] >= A[low]) {
// this will be only true if [low -- mid] range of array is sorted, and
// you can skip this portion, and continue looking to rest of array
low = mid+1;
}
in case 3, it should be [] high = mid [] , not [] high = mid-1 [] because if the average of high and low is odd, mid will never be [] (high+low)/2 + 1 []
How did you find the (n+mid-1)%n for the prev variable?
int findNumberRotation(int A[], int low, int high)
{
while(low
In 8:20 If change case3 and case 4 to
if(arr[low]
else if (A[mid] >= A[low]) low = mid + 1 ;
why A[mid] >= A[low], but not A[mid] >= A[high]
cause it doesnt work for arrays like [4,3,2,1]
if (A[mid]
at 05:34 why you have used equality sign also if array elements are distinct ?
Can someone explain me the question . ?
In test case: {15,22,23,28,31,38,5,6,8,10,12} and we are inserting 11 .
How is this a sorted array, as we have elements less than 38 (i.e., 5,6,8,10,12)
Can you please explain with this example ?
11 = length of array
low = 0; high = 10;
(arr[0] = arr[low])
low = mid + 1 = 6
low = 6 high = 10
arr[low]
Domenick D'Onofrio i mean i am confused with the question..
How many times is a sorted array rotated?
ex: original array {1, 2, 3, 4, 5}
rotated array {5, 1, 2, 3, 4}
Here the original array returns that it is rotated "1" time when we run the code. In his example code we are taking in an already rotated array and finding the number of times it has been rotated.
This is circularly sorted array. Anyway, you asked that question 2 years ago. How r u doing now?
Thank you
सही है भाई !
why there is "less than or equal to operator" instead of only "less than" in "case 1: A[low]
consider the case where array is --> [1]
The code goes in an infinite loop if the array is in reverse sorted order. Example: {6,5,4,3,2,1}.
Another simple line fixes the issue though.
Add a final else,
else low=mid+1;
It will handle all corner cases.
That is not a valid rotated sorted array. It has to be sorted in ascending order before it is rotated.
@@owlandahalf6681 It won't work in case of 5,4,3,1,2. Basically in case of A[mid] < A[low] and A[mid] > A[high], it will go into infinite loop as none of the if condition executes!
@@Achalshah20 again, that is not a rotated sorted array. If you rotate it to 1, 2, 5, 4, 3, you will see that it is not sorted in ascending order, nor is there any other rotation that works.
@@owlandahalf6681 You are right. The given solution should work if array is sorted in ascending order. (Given conditions that array is not rotated+flipped and array is not in descending order)
Why do you assume its sorted in increasing order?
mycodeschool Hi, If the 4th case holds true, doesnt that mean that the array is sorted and not rotated even once ?
Correct me please if I am wrong.
Think about a case where the array is rotated more than half the size of array, something like
{12, 13, 14, 15, 16, 18, 19, 1, 2}
Anshul Soni There are duplicates in your example so it won't work.
Reeti Garg I dont see duplicates unless you confused 1 2 in the end for 12 in the start.
I fixed my comment to make it not confusing
I think, we don't need case 4 .
thanks for the explanation.
in case 2:
why do you need to check next? I mean you know the array is cyclically sorted.
isn't it enough to check only prev in case 2?
prev = (mid +n -1)%n
if A[mid]
You said that we put 'prev=(mid+N-1)%N' so that prev doesnt get a negative value. Can you show a test case where it is possible?
Take mid = 0
If u cant get the module part
For example an array of 5 elements and the mid is 4
Prev = 4+(5-1) =9
We are passing our array size
We need to go the first element when we pass it
So we use % (the rest of the divide)
9/5 = 1 and the rest is 4 ( thats the modulo)
So index is 4 now :)
doesn't work if duplicates are involved. input - 345673
I think I have found an error in the algo.
2 4 4 4 5 6 8
circular form: 8 2 4 4 4 5 6, size=7
mid=(6+0)/2 = 3;
arr[mid]=4;
arr[prev]=4;
arr[next]=4;
now, arr[mid]
Well this algorithm doesn't work for duplicates.
couldnt understand the modulu part.....
Sir while finding prev,you have used prev=mid+N-1. Why did u add N? pls answer it
so that prev does not become negative
binary search approach is not working for some inputs for e.g {15,22,23,28,31,38,78,5,6,8,10,12} it is giving -1 as output . please correct me if i'm wrong.
This array is sorted circularly which is the case for this problem. But there is something wrong with the logic of this code. I am also getting such errors on InterviewBit.com
Your code looks not to be working for input [2,1]. Output should be 1. Can you check once
I think this algorithm would fail when there are two elements. say [2,1]. here, values for next and previous would be 0 and hence, it will return 0. But 1 is the right answer.
This algorithm fails when a n-sized array is rotated n times.
@@nishawadhwani909 then the array is in an 'unrotated' state
Bro you need to understand why he used that modulo part.
Cant we take the case 1 out of while loop?
this algorithm is not working for extreme case
int A[]={16,15,14,13,12,11,10,8,7,6,3,2}; // try with this array as input
this is not a valid input. Though not defined explicitly it is clear that the assumption is that the input dataset is sorted in ascending else the conditions will need to change though similiar logic will apply.
What if the array is rotated clockwise/rotated towards left? How to find out how many times it is rotated?
Volton007 check for the max ele
Your code is not running on my Mac ...😢
8:05 ....what did he say?
I am not getting adding N and modulo N???
it's clockwise, not anti clockwise
What problems can be solved by using this method in reality?
That's code interviewing in a nutshell!
Hope to run into sorted, rotated arrays some day lol
interview probs
what if we have similar elements(same value)?
if all the element is the same value, then the rotation will be a meaningless action.
but maybe there are several same elements, in that condition the example code will have bugs. we can change the condition to avoid bugs.
What in the case of duplicates?
use linear algorithm..
delete that last else case , otherwise u will get TLE in pure decreasing arrays like [4,3,2,1]
despite essentially copying everything to make sure I am not doing anything different, I am stuck in infinite loops :'(
Doesn't work for [3,1]
in your case mid as well as low is 3. so case 4 is applicable. Low becomes 1(low=mid+1).in next iteration low=high(case 1) and function returns 1.
আর সহেজেই করা যায় !!!
int FindRotationCount(vector &A)
{
int limit = A.size();
int n = A[0]; // when we find minimum value then return this index
for(int i=0;i
time complexity: O(n)
Not sure how the linear search code will work? If you take your example 12 2 3 5 8 11,, after the loop 11 will be in min.
How will 11 be in min? You start with min = 11, minIndex = 0. Go in loop compare with A[1] = 12, not lesser than min, so move on. Go to A[2] =1, lesser than min, so min is now 2 and minIndex = 2. Now we will not go inside if condition for any A[i]. So. min will be 2 after the loop.
mycodeschool I was taking the 12 2 3 5 8 11 case where it is rotated once,,
we start with min= 12 and minIndex=0, A[1]=2 and is less than min so we update min=2 and so on up to n-1=5 i,e 11. Since 11 is also less than 12 it will be stored in min.
ravi seetharam - And how exactly? When A[1] = 2, you are updating min. So now, min = 2, min Index =1. Next time for A[2] , A[3] and so on, we will not go inside the if statement because min is now 2.
@@ravindrabhatt Bhang peeke coding kar rahe ho kya
@@yadneshkhode3091 xD
what % operator did?
return the remainder
why pre=(mid+n-1)%n;
why not pre=(mid-1)??
Think what would happen for mid = 0. pre = -1 % n would be -1. and the code will throw an index out of bound exception.
It was clearly explained in the video itself at 6:40
It wont work on 6 5 4 3 2 1
becuase its not circularly sorted...for which above code is
Rohan Aggarwal not sorted
Code Fails to identity invalid array :
int[] arr = { 11, 12, 15, 1, 18, 2, 5, 6, 8 }
Deepesh Maheshwari thats not a rotated sorted array. 18 cannot be between 1 and 2