7 Number of Times a Sorted array is Rotated
Vložit
- čas přidán 10. 03. 2020
- Find the Rotation Count in Rotated Sorted array
Consider an array of distinct numbers sorted in increasing order. The array has been rotated (clockwise) k number of times. Given such an array, find the value of k.
Examples:
Input : arr[] = {15, 18, 2, 3, 6, 12}
Output: 2
Explanation : Initial array must be {2, 3,
6, 12, 15, 18}. We get the given array after
rotating the initial array twice.
Input : arr[] = {7, 9, 11, 12, 5}
Output: 4
Input: arr[] = {7, 9, 11, 12, 15};
Output: 0
PROBLEM STATEMENT LINK:www.geeksforgeeks.org/find-ro...
PLAYLIST LINK: • Binary Search | Interv... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
One small correction - if the sorted array is rotated only once, then min element (2 in this example) will be at last position(7 in this example) but returning 7 as result would mean that array is rotated 7 times, but actually its rotated only once. So correct answer should be = length of array (8 in this example) - index of min element(7 in this particular case that I presented) = 8-7=1.i.e., 1 time rotation.
Correctly noticed. For clock wise rotation it will be end-mid+1. For anti clockwise it will be mid.
Yes , I concluded the same
this logic he explained is for right rotation so min element i.e, 2 will be at index 1 if the array is rotated once and will be at 7 th index when it is rotated 7 times
Always used to get confused among conditions how to apply. Got the clear crystal understanding now. Thank you so much for delivering such an amazing content.
if(arr[mid]
why is that ?
can you please explain.
Everyone have a doubt , for example we reach a condition where array is sorted then arr[start]
why should we do end = mid-1 if array is sorted?
@@aabirchakraborty3033 : Because we are trying to find the minimum element. So if the array is sorted, the minimum element will always be towards the left. Thanks.
class Solution{
public:
int findKRotation(int arr[], int n) {
// code here
int start = 0, end = n-1;
while(start
@someshsangwan3768 directly return start in case of else if(arr[start]
in the case of special condition
else if(arr[start]
Here’s the gist of logic used:-
1. To find the number of rotations in a rotated sorted array, we need to find the index of the minimum element, so this question gets converted to finding the index of the minimum element.
2. We need to mention one exceptional case here, that if the array is properly sorted (0 times rotation), then we can return 0 in such cases. Now, the minimum element possess a unique property here that it is less than both of its adjacent elements, and that is also quite obvious. So as usual we’ll check the mid element if its less than its previous as well as its next element. If it comes out to be like this, then it is surely the minimum element, and we’ll return its index. One thing we need to take care about is, suppose my mid is pointing to index=0, then how I’ll reach to its previous element, assuming that its previous element will be the last element (since it is also a rotated array), then for fetching its previous element, we need to do prev=(mid+n-1)%n, here mid+n-1 will give me n-1 and (n-1%n) will be n-1, which is the index of the last element. Similarly, if my mid is pointing to the last element, then its next element has to be the first element of the array, so for that do next=(mid+1)%n. By doing this, we can avoid out of bound situations.
3. Now, if the mid element doesn’t comes out to be the minimum element, we have to move to either side of the array, to pursue the binary search algorithm. We need to move to that part of the array which consists the minimum element, because that’s what we’re finding. Suppose my array is:- 6, 8, 9, 10, 1, 3 ,4 , then mid=3(which is pointing to 10), this mid is not the minimum element, so my array gets divided into two parts, one is (6,8,9,10) an the other is(10,1,2,3), as you can see one part is sorted and the other one is unsorted, so my minimum element always lies in the unsorted part and this is true for every case. So I’ll be moving to this unsorted part of the array.
4. How can I decide which part is sorted and which is unsorted, then only I can proceed moving to the unsorted part in order to find my minimum element. For that, we need to check whether my first element is smaller than the mid element or not, if arr[0]
but here is also a catch int l=0,h=n-1;
while(l
how do you guys have the patients to write this much i can't even read it
@@LostHero1 Normally such ppl sit in the 1st or 2nd row in the class.
@@MrAtul61 loll
you gain my heart
how many of u are actuall practicing by writing code after watching aditys's video?
Many people stated that there is PROBLEM in the solution given by Aditya Verma sir.
BUT there is NO problem, only some simple variations could lead to more perfect solution according to given question type. READ BELOW POINTS
1) Is the array/list: 'left-rotated' or 'right-rotated' ?
if 'left-rotated' -> return 'n-mid'
else if 'right-rotated' -> return 'mid'
2) We need to check only 'previous' element of mid, for claiming it to be smallest element, as the mid would obviously be smaller than the next element (as its sorted array/list)
if arr[mid]
How to check if it is left rotated or right rotated
And ans will be n-mid+1 if it is right rotated
@@yash_______105 It will be given in the question, that whether it is right rotated or left rotated, if not, you can assume with the help of given example, and that assumption would give you the correct ans.
why are we checking like
@@harikasai273 Hey !
I guess there won't be any difference in the output either you do
@@himanshukhairajani it's failing if it's rotated once like [3,1]
If we had rotated it 5 times, then the position of minimum element(which is 2) would be index 3, which is not equals to no. of times the sorted array was rotated(which is 5) right ????? . The answer should be = (length of array - index of minimum element)
This is right code
class NoOfRotation{
public int fun(int arr[]){
int start=0;
int end=arr.length-1;
while (start
@@rkalpeshk will this code work if we have repeated elements?
@@parthkumar1033 No it doesn't work for array 18 18 18 18 2. The answer must be 4 but according to this code the answer is 2.
@@madhavmundhra2698 hmmm
It's for anticlockwise rotated array. He actually mistakenly said it for clockwise one.
Bro u explained code for anticlockwise rotation then index of min element is equal to no of times array is rotated. But in video example u described clockwise rotation... Anyways learning all these concepts is fun. And it was a enjoyable ride learning dp from u
Yeah...I was feeling the same..thanks for pointing it out...
True
Thanks for pointing it out.
Can you explain how rotating array the different way results in a different rotated array...Can you give an example performing both rotations on the same array.
@@kirtikhohal3313 In clockwise just we return index ...BUT in Anticlockwise We return (N-index ) which is applied in this problem .....Code and check 👍🏿👍🏿
Awesome tutorial love it !!!, Thanks
really the way you are explaining is amazing , step by step. Thanks a ton Aditya. My friend recommended to watch your playlist of DP and Binary search, and I loved it.
++
Thanks for explaining in such a easy manner !!
@Aditya Verma sir if array contains duplicate elements also then what should be the approach.Please answer.
Great explanation .Loved your content.
Sir, why u stop uploading such vedios students like us want more these type of vedios ..please also upload for graphs and all DS ALGO...
Thank Very much. 🙌🙏.
I think you should attend English classes before DSA
@@manishmalik. Grow tf up dude. Not everyone is lucky enough to be born in a full fledged english speaking family like yours, at least I wasn't. Since we're on the topic of taking English classes, you probably need some revision of punctuations? It's taught in class 5th, right? IDK just a suggestion.
@@manishmalik. You should go to USA and work as a waiter. Good english is needed there, please f off there.
@@sohamshah2127 chal chal nikal, baap Ko mat sikha
@@manishmalik. english me bol bhai, dsa interview kaise nikaalega varna
Thank You for this Beautiful Explanation
this code will give WA on certain cases like " 5 6 7 8 1 2 3 4" because we are looking for "unsorted" and "sorted" half, but there will be cases when our entire range will be sorted and for that case we need to go left. here is my implementation:
int findRotation(vector& a)
{
int n = a.size();
int low = 0, high = n - 1, res = -1;
while(low 1) // when our range is greater than 2
{
if(a[mid]
no it doesnot
If I want to find max element in my rotated sorted array , then the crux would be the element which is greater than both of its adjacent element. And if I want to find number of rotations through the index of max element, then it would be index+1.
It's May now.Please upload your other tutorials.
Your content is greatly helpful.
Thank you so much .
Trying my best, its just the lockdown which has put me off my track.
@@TheAdityaVerma yes sir!!! plz continue with the stack playlist!!!!! Eagerly waiting
A very early to follow explanation @Aditya thanks a ton!.
Just a simple addition to cover the corner case which your video missed. In case of:
1. zero rotated array
2. when mid lies in the sorted subarray.
we need to add one more condition in the while loop:
condition to check if mid is smaller than neighbors
if(arr[start]
edit: a better way is just checking if arr[start]
@@ankushmahajan1960 v.nice.....and clear, thanks bro!!
code: the array is right rotated. one more condition you need to consider is when array is sorted.
int findKRotation(int arr[], int n) {
// code here
int s=0;
int e=n-1;
while(s
but why is this condition necessary -
else if(arr[s]
Hey Bro you are doing great work . can you tell me if it is possible to use this method for duplicated array?
Obviously this algorithm will not work for duplicates elements.
This particular algo which is being told in the video will also not work if array is rotated differently. You need to interchange else if condition.
This below code worked for me in the Leetcode question 153. Find Minimum in Rotated Sorted Array with all test cases passed.
Here I'm returning minimum element in the array not the index.
int findMin(vector& nums) {
int n = nums.size(); //Taking array size
int low = 0 , high = n-1; //Initializing our low and high variable
if(low == high) return nums[low]; //If array contains only one element
if(nums[low]
Not sure how this passed, I don't think this will work even for a simple test case [4,5,6,7,0,1,2]
@@kumarvivek02 I don't know what made you think that but the code is correct and it's working. It's giving the correct output. I think you've missed the point I've written that I'm printing the minimum element in the array. Acc to the given question: number of rotations = index of minimum element
@@kumarvivek02 This below code will work for you. It'll print number of rotations
int findMin(int *nums, int n)
{
int low = 0, high = n - 1; // Initializing our low and high variable
if (low == high)
return low; // If array contains only one element
if (nums[low]
firstly, I think on gfg as well as on leetcode, it is pretty mentioned that all the elements of the array are unique or distinct.
And can you elaborate more about directions of rotation, and why the code in the video will not work if array is rotated differently. How the array can be rotated differently?
Very nice explanation. Thanks
kudos to you , you made it crystal clear.
int arr[] = { 30, 2,10, 10, 10, 10, 20 }; for this case the answer will come as 10, but its 2 so we need to use
if (arr[mid]
To conclude, we are reducing the problem of finding the number of times the array has been rotated to the problem of finding the index of the minimum element in the rotated array.
Brother your explanations are so that I was able to figure the solution after hearing the problem statement. Love u 3000 bro❤️
ye iron man ka chod idhr mt faila smjhe
I think instead of index of minimum element it should be, length - ind of minimum element. This is for clockwise rotation
right
simple approach
int binarySearch(vector a,int s,int e){
while(sa[e]){
s=mid+1; //minimum element is in the right part
}
else{
e=mid; //minimum element is in the left part
}
}
return s ; //smallest element index;
}
My girlfriend: mom says no girlfriend....lollll
😂
Very Nice Explanation.....Keep making videos
logic is partially correct, it misses many testcases
Literally , I have observed , bhaiyya aap puri koshisk krre ho kebaccho ko JEE wali feelings se pdhao.
Hats off to your intentions 🙏🏻🙏🏻
Aditya you have made a slight error by comparing arr[mid] with low and high to decide whether to go left or right depending on which is unsorted.
It will fail for the test case like [4,5,6,7,0,1,2]
Actually you need to compare arr[mid] with first and last element rather than low and high to decide whether to go left or right.
One can try leetcode problem:-
153. Find Minimum in Rotated Sorted Array
class Solution {
public:
int findMin(vector& arr) {
int lo=0, hi=arr.size()-1;
int mid;
int prev, next;
int n=arr.size();
if(arr[0]
this code is accepted and also works for this case too
class Solution {
public:
int findMin(vector &num) {
int start=0,end=num.size()-1;
while (start
@@Aditya-pl3xg yes good way of using start and end.
Unlike what he has taught in the video.
yes you are correct for checking whether its sorted or unsorted we will compare mid value with 0 and n-1 values
for duplicate array?
You are wrong.
this will work too-
public static int findMinIdx(int[] nums) {
int start = 0, end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (nums[mid] > nums[end])
start = mid + 1;
else
end = mid;
}
return start;
}
Adi , your explanation is awesome!
just checking for prev term would be enough right?
The logic of this code itself is very good
There is just a small bit of logic which needs to be added to make it sustainable for all cases.
Given we are choosing the unsorted array every time. It might happen we find a array sorted on both the sides of the middle.(array with 3 elements [1 2 3] )
For eg. in [4,5,6,7,0,1,2]
After the first iteration the arr[middle] comes out as 1.
Now the array [0,1,2] is sorted on both sides. To deal with this add another condition if (arr[first] < a[last]) return arr[first];
Here is the C++ code for the same. This code returns the minimum. After finnding the minimum one can return the clockwise and anticlock wise rotation.
int findMin(vector& nums) {
int first=0;
int n=nums.size();
int last = n-1;
int middle=0,prev=0,next=0;
while (first
@@latika7040 Took me 2 cups of coffee and good 4 hours to get this question going…. Lmao ded
Nice one buddy🙌
thanks a lot dude, i was stuck on this on leetcode.
Thanks bro for making it crystal clear just a slight modification in your code we need to return index of smallest element but you have returned nuns[middle] and nuns[first] by mistake I guess so we must return middle and first other than this your explanation was on spot thnks
@@adityaraj-md8pb Yup this code returns the minimum and not the position
thanks brother good explaination
Nice explanation sir...
can anyone tell when this is rotated by 1 the index of 2 wiill become 7 then how we calculate the rotation
So the solution which he has explained is applicable only when array is rotated anticlock wise...however the example which he showed is of clockwise rotation..so its wrong
Consider an array sorted be 1,2,3,4,5,6,7,8,9 Now let us say that in question it's given 3,4,5,6,7,8,9,1,2 According to your concept index of the minimum element is 7 but array is rotated only 2 times. You should return min(m,n-m) but it's fine ..You are doing a wonderful job bro!! Keep it up. Please take this comment as a thread of trust on u that how can u forget this?
Answer should be (length of array - min number index)
@@souravbera1465 it depends upon the direction of rotation
@@souravbera1465 it shoudl be (length of array - min number index) % length of array. This is because if we consider the case in which the array is not rotated at all that is the array is 1,2,3,4,5,6,7,8 then in this case the length of the array is 8 and the index of the minimum element is 0. so according to your logic the answer would be 8 - 0 = 8 but the actual answer is 0. This discrepancy can be solved if we take the mod of the answer from the length of the array.
Although it might be possible that the questions considers 8 also as a valid answer.
Really loved the explanation. Are you planning to upload problems based on Graphs? If yes? then when?
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
@@TheAdityaVerma this is not working if given array is sorted and also if duplicates elements are there .pls help,pls reply
@@TheAdityaVerma sir may ab khatm hone wala hai.... we All r waiting sir...
♥♥
@@TheAdityaVerma June aagaya bhai.
I'm still waiting 😯
@@TheAdityaVerma bhai august aa gaya ab toh kar do plzz aap hi sahara ho placement aa chuki hai
just a small addition add the following line inside while loop before calculating mid
if(arr[start] < arr[end]) return start;
or you can swap the order of if and else if statements, the one with end = mid -1 should be at top then do start = mid + 1
can you help with the intution behind the same. Let's say we have an interview and we have to explain why we either did "if(arr[start] < arr[end]) return start;" or did the unusual step of putting "end = mid -1" above.
Thanks
No one is gonna talk about earthquake?
it was hilarious man lol
Bro we don't have to return index of smaller element.. We have to return (arr.size() - index of smaller element) ..
Thankyou so much sir your explaination is so good
❤ Bhai, great explain.
Thank you very much. You are a genius.
if array is rotated more times then the size of the array how would we return the rotation count?
e.g.: [2,3,4,1] let’s say i have rotated this 8 times but i think we always return 4?
This is the simplest :
while (left < right) {
int mid = left + (right - left)/2;
if (nums[mid] > nums[right]) left = mid+1;
else right = mid;
}
// left==right is the index of the smallest value and also the number of places rotated.
amazing
int findKRotation(int nums[], int n)
{
int low = 0, high = n-1;
while(low < high)
{
int mid = low + (high - low)/2;
if(nums[mid] > nums[high])
{
low = mid + 1;
}
else
{
high = mid;
}
}
return low;
}
please tell if it a good way to approach this problem or not?
Got accepted on GFG and leetcode.
Do we have to put first element at last in one rotation( 5 6 8 11 12 15 18 2) or put last element at first( 18 2 5 6 8 11 12 15) as in first case... Ans is size-index of min element but in second case it is index of min element.
We can also check neighbouring elements instead of start and end to get if the element is peak/pivot or not.
If left neighbour is greater and right is smaller it means it's still decreasing and element is on the left and vice versa.
Suppose if the array is rotated only one time and now the index of 2 is 7.....so should it be the answer that 7 times the array is rotated??
Sir,how are you finding prev and next part.can you please explain
does this not work for the case when some of the elements are equal in the sorted array .. like 0 1 1 1 1 is rotated to 1 0 1 1 1 etc ..
what if the array has duplicate elements?
thank you bhaiya your explantion is very great. 😊
Earthquake aagya tha lol...love you bro keep posting such amazing playlist!
In the middle of the search if we found a sorted non rotated part. this code will not work on that. For example on [4,5,6,7,0,1,2] this test-case
what if we use built in function(for python users) to find the minimum number in the array ???
will the time complexity increases???
yes It will . I also thought that first but when I check the time complexity of "min" and "max" it is O(n) ,
which will make our solution time complexity O(n)
you can read this : wiki.python.org/moin/TimeComplexity
Hey, below code is to be added in middle if at 22:31
if (array[start] = array[end]) {
low = mid + 1;
}
There is one problem in the solution explained by Aditya.. Consider this example:
A = [11,12,15,18,2,5,6,8]
when A[mid] = 18, A[start]
Solution is great but I would add one more approach....We can also solve by finding peak in array using BS and returning index(peak)+1
[11,13,15,17]
try your approach in this arr
it wont work and is incorrect
Hello, I am not understanding how (# of rotations) = (index of min elem).
Eg: arr[] {2, 5, 6, 8, 11, 12, 15, 18}
index of min elem = 0 = # of times arr was rotated = 0
ok now if I rotate arr once,
arr[] = {5, 6, 8, 11, 12, 15, 18, 2}
now index of min elem = 7
but number of rotations = 1
so in this case I get (index of min elem) != (number of rotations)
Am I missing something? Can you please clarify ?
That should be n-idx of mid , if we are rotating anticlockwise and it'll be index of mid if we're rotating clockwise
Bhaiya Boundary cases ke liye output wrong aa raha hai..
Help
will this code also take care of repeating elements in the array?
what if the no of rotation is one and min element is at last index?
i think we will always be checking mid element with the extreme elements of the array and not the extreme elements at that time of execution..........means start and end will be changing here but we will always be comparing mid with arr[0] and arr[n-1] in the second and third else if blocks inside the while loop
int findKRotation(int arr[], int n) {
int l = 0, h = n-1;
int l1 = l,h1 = h;
if(arr[l]
yup! I think he made a mistake there.
will it wrong if we return (size-index) i.e 8-7=1(1 time rotation) i.e 8-4=4(4 times rotation which was special case)
Great work dude
Nice Explanation bahut sara video upload karo mai sab dekhunga
what i observed
if right rotation is there then return n-mid ex: {4,5,6,7,8,1,2,3 }
if left rotation is there 8,7,6,5,4,1,2,3 the use return mid
u can analyse also using index
public class FindNumberOfTimesSortedArrayRotated {
private static int findNumberOfTimesSortedArrayRotated(int[] arr, int n) {
int start = 0;
int end = arr.length - 1;
int next = 0;
int prev = 0;
while (start = arr[mid] && arr[mid]
amazing brother thanks a lot
Sir I am big fan of your teaching style and your concept building sequence. i will watch all of your videos . great energy sir ji.
So people are saying that there is problem in aditya's solution. at last as he mentioned that you have to take care of an edge case where array is already sorted or while searching you have reached in a region where array is sorted ,you have to take care of that case , simply check a[mid]>=a[start]&&a[mid]
humse *chaite* h ki hm binary search lgaye , too good bhai
How it would work for suppose array(6,1) ?
Bhaiya elseif wali condition m arr[start] m start to update ho jayega uski jagah first index arr[0] ayega or ese hi last index arr[n-1] se compare hoga
The code provided in video will fail if the array is rotated 0 times. i.e if array is perfectly sorted. Is it always assumed that the array is rotated atleast 1 time?
thats why we are checking at the start only. i.e if arr[start] < arr[end] then return arr[0]
bhaiya this code will not work in case of duplicate elements,then your base condition will not satisfy
But when the array is sorted, without rotation, then the minimum element lies in sorted array part.
2,5,6,8,11,12,15,18
Mid element is 8 which is greater than arr[start] so sorted part is left side array with respect to mid element. And there lies the minimum element.
this is a sorted array the condition arr[mid]
how come rotation equals index of min num? if its rotated once, the index of min elem is the last element
Here in 17:10 ...if we can see that start is greater than end ...then how will the while loop work here ...as its conditions is start
I am not understanding why the above-explained code returns 0 for the test case: 11 12 15 18 2 5 6 8, instead of 4
different but a little bit simple code in c++, can't thank him enough.
while(ends>=start){
mid=(ends-start)/2 +(start);
if(ends==start){
pos=start;
break;
}
if(nums[mid]
ATTENTION THERE IS MISTAKE IN THE CODE !!! (above code will not pass for every testcase on gfg, will give WRONG ANSWER)
else if(arr[start] else if(arr[start]
if the array rotated 1 time then the minimum element gets the last index but u said number of rotation is equal to the min index, shouldn't it be length of array-index of min element
Bhai earthquake 😂😂op yaar !!!
Alag level ka banda hai bhai tu!
we can also do it by finding peak(max) element .
can you tell why minimum element always in unsorted part,it's observation or reason
Both.
@@manikanth.8507 can you elaborate?
Observation
NICE SUPER EXCELLENT MOTIVATED
The explanation completely works
Here's the code:
int smallest(int arr[],int beg,int end)
{
int n=end+1;
if(beg==end)
return beg;
int mid=beg+(end-beg)/2;
int next=(mid+1)%n;
int prev=(mid-1+n)%n;
if(arr[mid]arr[mid])
return mid;
else if(arr[end]>arr[mid])
return smallest(arr,beg,mid-1);
else return smallest(arr,mid+1,end);
}
will the first if condition work for this input [5,5,5,1] this will return 5 but ans is 1.
The elements should be distinct, also mentioned in the problem statement.
very lucid explanation
what if there are duplicates? will it handle?
Thankyouuuuuu veryyyyyy muchhhh .
Amazing explanation of how to think or find out any problem 👏🏻