How many times is a sorted array rotated?

[@Thanapat086]

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

[@harsh.sharma]

Thanks a lot!! This was really required! 🙏

[@shikhajain5833]

Well explained👍🏻

[@abraarz2971]

Thanks

[@rayeugene8139]

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

[@drakemaddox8249]

@Ray Eugene Instablaster ;)

[@mycodeschool]

Thanks for noticing Sudarshan !!

[@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 (=)

[@zhiyaowang8826]

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

[@vandananayaknayak5511]

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

[@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.

[@jameskelly132]

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.

[@xof8256]

true

[@vinaypednekar680]

what if your next element is greater ? that's why pivot property

[@siddharth__pandey]

@@vinaypednekar680 then it would not be a circularly sorted array

[@downtowngedi]

True, I don't think there is any need to check the next element, checking prev element is enough.

[@thahirThavvagunta]

Wt you said is correct

[@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

[@adarshverma3372]

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; } } }

[@sahu059]

I just have doubt regarding pivot statement A[mid]

[@igboman2860]

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

[@swaw11]

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

[@rishugoyal7970]

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]

[@pranavganorkar2379]

Hi Animesh...can we write the case for a[mid]

[@no-body7286]

to solve edge cases like if there is one array

[@abhishekguptasarma2060]

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

[@vikramadityavardhan4067]

Dude he's not dead his colleague is

[@killerboy-mz9bd]

@@vikramadityavardhan4067 what's channel owner name?

[@ugh657]

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.

[@siddhantdeshmukh7120]

hmm nice one.more efficient

[@aakash4351]

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.

[@igboman2860]

@@aakash4351 it is still O(logn)

[@ivandrofly]

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

[@dankyt9249]

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

[@DilipkumarGangwar]

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

[@ambarishguntupalli5152]

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

[@ShivamAroraa]

think when low = high e.g. Array = [1]

[@ambarishguntupalli5152]

@@ShivamAroraa I think we need

[@tarandeepsingh8704]

@mycodeschool was, is, & will be the best channel ever!

[@abhishekkasam6685]

Thank you so much broo u have clarified my all the doubts

[@dingusagar]

def findMin(A,l,h): if A[l]

[@sudarshan14sipu]

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

[@Wheelz_for_Feelz]

What is the use of taking A[low]

[@ashishshah9006]

consider the case where array is --> [1]

[@thahirThavvagunta]

This case is when array rotated zero times

[@captain_vegan]

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]

[@abocidejofa9686]

thanks. great explanations

[@ravisrivastava666]

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.

[@sharangkulkarni5718]

सही है भाई !

[@alphazero0]

hey can anyoe explain me whats the reason for (mid+1)%n? and also (A[mid]

[@rpodder]

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]

[@alphazero0]

@@rpodder actually mid=n-1 case comes only when l=n-1 h=n-1, in this case, the first case if(A[l]

[@rpodder]

@@alphazero0 Oh, yes. What you said is correct. 👏

[@alphazero0]

@@rpodder and whats the reason for A[mid]

[@nguyenhung2441]

int findNumberRotation(int A[], int low, int high) { while(low

[@PanicIGaming]

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 []

[@Varaprasad865]

Thank you so much

[@user-mi8ew2to8e]

Why do you assume its sorted in increasing order?

[@kamalsmusic]

How did you find the (n+mid-1)%n for the prev variable?

[@srikanths5227]

Great Explanation but the fourth case mentioned if(A[mid] >= A[low] is wrong. It should be A[mid] >= A[high].

[@sarjeet91]

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; }

[@nilofermehta3781]

Hi just wondering that you said the condition set is "no duplicates" then why are you checking in case 1 that A[low]

[@neerajjoshi9493]

no, in worst case, low and end index can simultaneously reach the pivot. for that case we need to write a[low]

[@sarthakjoshi3797]

@@neerajjoshi9493 I didn't get you. Can you explain more clearly?

[@aayushwadhwa3788]

@@sarthakjoshi3797

[@ashishshah9006]

consider the case where array is --> [1]

[@roopkishore785]

why there is "less than or equal to operator" instead of only "less than" in "case 1: A[low]

[@ashishshah9006]

consider the case where array is --> [1]

[@tarun4705]

doesn't work if duplicates are involved. input - 345673

[@AP-eh6gr]

is the modulo part even necessary? the while loop runs 'while' low

[@neerajjoshi9493]

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

[@dongxie4756]

if (A[mid]

[@niharikaepuri3305]

In 8:20 If change case3 and case 4 to if(arr[low]

[@RT-jd9dw]

Your code looks not to be working for input [2,1]. Output should be 1. Can you check once

[@SidharthJhawar]

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.

[@anshulsoni477]

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}

[@reetigarg7398]

Anshul Soni There are duplicates in your example so it won't work.

[@anshulsoni477]

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

[@abhiragkesarwani2293]

I think, we don't need case 4 .

[@manojpandey7517]

at 05:34 why you have used equality sign also if array elements are distinct ?

[@srinadht7238]

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 ?

[@domd511]

11 = length of array low = 0; high = 10; (arr[0] = arr[low]) low = mid + 1 = 6 low = 6 high = 10 arr[low]

[@srinadht7238]

Domenick D'Onofrio i mean i am confused with the question..

[@domd511]

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.

[@MridulBanikcse]

This is circularly sorted array. Anyway, you asked that question 2 years ago. How r u doing now?

[@MultiTalvin]

couldnt understand the modulu part.....

[@abhijitpaul7683]

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]

[@vikku_19]

Well this algorithm doesn't work for duplicates.

[@amitprasad3495]

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?

[@siddharth__pandey]

Take mid = 0

[@gokulnaathbaskar9808]

Thank you

[@expertreviews1112]

it's clockwise, not anti clockwise

[@nachiketakumar3841]

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.

[@utkarshsaxena8034]

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

[@anjana1700]

Sir while finding prev,you have used prev=mid+N-1. Why did u add N? pls answer it

[@shashishekhar8336]

so that prev does not become negative

[@PraveenKumar-tx4od]

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.

[@nishawadhwani909]

This algorithm fails when a n-sized array is rotated n times.

[@harsh.sharma]

@@nishawadhwani909 then the array is in an 'unrotated' state

[@harsh.sharma]

Bro you need to understand why he used that modulo part.

[@samyakkumbhalwar4296]

Cant we take the case 1 out of while loop?

[@Arka161]

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.

[@owlandahalf6681]

That is not a valid rotated sorted array. It has to be sorted in ascending order before it is rotated.

[@Achalshah20]

@@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!

[@owlandahalf6681]

@@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.

[@Achalshah20]

@@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)

[@basabmukherjeeclass12bci29]

Your code is not running on my Mac ...😢

[@daitavan297]

What problems can be solved by using this method in reality?

[@slikdude12592]

That's code interviewing in a nutshell!

[@cyberpsybin]

Hope to run into sorted, rotated arrays some day lol

[@ananths5905]

interview probs

[@karthikperavelli1735]

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

[@sohailsayed23]

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.

[@Volton007]

What if the array is rotated clockwise/rotated towards left? How to find out how many times it is rotated?

[@shreevatsalamborghin]

Volton007 check for the max ele

[@robtangled8816]

8:05 ....what did he say?

[@salemouail627]

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 :)

[@gauravkumarsoni3095]

I am not getting adding N and modulo N???

[@Joyddep]

What in the case of duplicates?

[@ronitmishra8917]

use linear algorithm..

[@asishpatra7556]

what if we have similar elements(same value)?

[@涛哥涛哥-i1p]

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.

[@savar33]

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]

[@gyanasahu1006]

Doesn't work for [3,1]

[@075_ritikkumar7]

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.

[@Chris-cs7nv]

despite essentially copying everything to make sure I am not doing anything different, I am stuck in infinite loops :'(

[@amritkanoi8804]

delete that last else case , otherwise u will get TLE in pure decreasing arrays like [4,3,2,1]

[@rohan9354]

It wont work on 6 5 4 3 2 1

[@dipanshu2310]

becuase its not circularly sorted...for which above code is

[@shreevatsalamborghin]

Rohan Aggarwal not sorted

[@mdshahidulislam3982]

আর সহেজেই করা যায় !!! 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

[@rpodder]

time complexity: O(n)

[@ravindrabhatt]

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.

[@mycodeschool]

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.

[@ravindrabhatt]

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.

[@mycodeschool]

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.

[@yadneshkhode3091]

@@ravindrabhatt Bhang peeke coding kar rahe ho kya

[@gamoholic7653]

@@yadneshkhode3091 xD

[@shakiulanam6569]

why pre=(mid+n-1)%n; why not pre=(mid-1)??

[@BrajeshKumardreamer]

Think what would happen for mid = 0. pre = -1 % n would be -1. and the code will throw an index out of bound exception.

[@bijjalavenkateswarlu9306]

It was clearly explained in the video itself at 6:40

[@sagar7958]

what % operator did?

[@nguyenhung2441]

return the remainder

[@DeepeshMaheshwari17feb]

Code Fails to identity invalid array : int[] arr = { 11, 12, 15, 1, 18, 2, 5, 6, 8 }

[@paulchino81]

Deepesh Maheshwari thats not a rotated sorted array. 18 cannot be between 1 and 2